Sieve of Eratosthenes In PHP

By philipnorton42 on 5th July 2013

The sieve of Eratosthenes is named after Eratosthenes of Cyrene who was a Greek mathematician who devised a mechanism to find a sequence of prime numbers using a simple algorithm.

Normally, looping through a list of numbers and finding the primes can be an expensive process. The seive of Eratosthenes is one of the most efficient way of working out all of the smaller prime numbers below (below 10 million or so).

The sieve works by looping through a list of consecutive numbers, starting at 2. For each number in the sequence the multiples of that number are marked to be removed from the list of numbers. When finished the numbers that are not marked are prime numbers.

This algorithm is pretty straightforward, but from that it is possible to create a simple PHP function that will generate all the prime numbers up to a given number.

/**
 * Find all the primes up to a given number using the seive of Eratosthenes algorythm.
 *
 * @param $finish The number to stop searching for prime numbers.
 *
 * @return array The array of prime numbers.
 */
function find_primes($finish) {
 
  // Initialise the range of numbers.
  $number = 2;
  $range = range(2, $finish);
  $primes = array_combine($range, $range);
 
  // Loop through the numbers and remove the multiples from the primes array.
  while ($number*$number < $finish) {
    for ($i = $number; $i <= $finish; $i += $number) {
      if ($i == $number) {
        continue;
      }
      unset($primes[$i]);
    }
    $number = next($primes);
  }
  return $primes;
}

Here is an example of the function in use.

print_r(find_primes(20));

This generates the following output.

Array
(
    [2] => 2
    [3] => 3
    [5] => 5
    [7] => 7
    [11] => 11
    [13] => 13
    [17] => 17
    [19] => 19
)

With a small amount of modification it is possible to create a function that will return an array containing a range of prime numbers. Because of the way in which the algorithm works is isn't possible to generate just a selection of numbers, the numbers must all be generated and then just the prime numbers needed must be split out of the array.

/**
 * Find all the primes up to a given number using the seive of Eratosthenes algorythm.
 *
 * @param $start The number to start searching for prime numbers.
 * @param $finish The number to stop searching for numbers.
 *
 * @return array The array of prime numbers.
 */
function find_primes_range($start, $finish) {
  // Initialise the range of numbers.
  $number = 2;
  $range = range(2, $finish);
  $primes = array_combine($range, $range);
 
  // Loop through the numbers and remove the multiples from the primes array.
  while ($number*$number < $finish) {
    for ($i = $number; $i <= $finish; $i += $number) {
      if ($i == $number) {
        continue;
      }
      unset($primes[$i]);
    }
    $number = next($primes);
  }
 
  // Slice the array into the given range
  foreach ($primes as $prime) {
    if ($prime < $start) {
      unset($primes[$prime]);
    } else {
      break;
    }
  }
  return $primes;
}

This can be used in the following way.

print_r(find_primes_range(20, 50));

Array
(
    [23] => 23
    [29] => 29
    [31] => 31
    [37] => 37
    [41] => 41
    [43] => 43
    [47] => 47
)

Comments

Permalink

Alex - Fri, 05/15/2015 - 18:51

This wil produce a memory error when you try anything over 1 mil :( i was hoping to go from 2 to 100mil with this for a comparison.

Permalink

Alex - Fri, 05/15/2015 - 18:56

To add to that, there may be a memory leak somewhere here

Permalink

philipnorton42 - Sat, 05/16/2015 - 20:18

I wouldn't use this function to calculate numbers that high, especially not with PHP. You could always use gmp_nextprime () (http://php.net/manual/en/function.gmp-nextprime.php) I suppose?

Add new comment

Add new comment