Skip to content

Prime numbers in PHP

This is quite fast (but unfortunately memory consuming) algorithm for generating all prime numbers up no n:

 
 
  $n = 100; //this is the upper limit
 
  for ($i = 2; $i <=$n; $i++){
    $primes[] = $i;
  }
 
  foreach ($primes as $num){
    if ($num != 1){
      $step = $num;
      for ($i = 2*$num-2; $i <= count($primes); $i= $i + $step){
        if ($primes[$i] != 1) {
          $primes[$i] = 1;
        }
      }
    }
  }
 
  $primes = array_unique($primes);
  $primes = array_values($primes);
  sort($primes);
  unset($primes[0]);
 

I found this on Wikipedia here. It needs optimization (for example count($primes) doesn't need to be called on every iteration) but helped me a lot for solving some Project Euler problems.