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 N 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;
}
