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