Friday, December 16, 2011

Finding prime numbers with in a given number n.

I stumbled upon this question in Interviewstreet.com - looked very basic question, however I tried attempting it to check their editor. Later found that this was good question than I thought. The problem arises when N is = 1000000. We have to manage both memory and execution time.

For execution time to be optimized, used this algo for finding the prime numbers with in a given number. For memory modified it further to work in steps of 100000.
-------------------------------------
Write a function getNumberOfPrimes which takes in an integer as its parameter,
to return the number of prime numbers that are less than N

Sample Testcases:
Input #00:
100
Output #00:
25

Input #01:
1000000
Output #01:
78498
----------------------------------------
Below is the solution. I have used php. I would add comments and optimize those loops further when I get some free time later.

function  getNumberOfPrimes(\$n) {
\$count = 0;
\$prime = array();
//optimization for memory split the number in to sub groups of 100000
\$step = 100000;
\$maxitr =  floor(\$n/\$step);
\$itr = 0;
\$prime = array();
\$lastprime = 2;

do{
\$numbers = array();

if(\$itr){
\$start = ((\$itr)*\$step)+1;
}else{
\$start =2;
}
if(\$itr == \$maxitr){
\$end = \$n;
}
else{
\$end = (\$itr+1)*\$step;
}

\$len = sqrt(\$end);
\$numbers = array_fill(\$start,(\$end-\$start),true);

if(count(\$prime)){
foreach(\$prime as \$value){
\$multiplier =  floor(\$start/\$value);
for(\$j=\$value,\$remove = \$j*\$multiplier;\$remove<\$end;\$multiplier++){
\$remove = \$j*\$multiplier;
\$numbers[\$remove]=false;
}
}
\$lastprime = end(\$prime);
}

for(\$i=\$start;\$i<=\$len;\$i++)
{
if(\$numbers[\$i]){
for(\$j=\$lastprime,\$remove = \$j*\$i;\$remove<\$end;\$j++){
\$remove = \$j*\$i;
\$numbers[\$remove]=false;
}
}
}
for(\$i=\$start;\$i<\$end;\$i++){
if(\$numbers[\$i]){
\$count++;
\$prime[] = \$i;
}
}
\$itr++;
}while(\$itr < \$maxitr);

return \$count;
}
-----------------------------------