« Home | Javascript performance. » | Sorting algorithms. » | Multi tenant challenges. » | Web application security. » | Another short but beautiful game I won. » | Javascript dom » | Javascript. » | Loading scripts asynchronously. » | Chess rules » | A good recent game that I won. » 

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