Sieve of Eratosthenes In PHP

5th July 2013 - 4 minutes read time

Note: This post is over a year old and so the information contained here might be out of date. If you do spot something please leave a comment and we will endeavour to correct.

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
)

array

Comments

Permalink

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

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

Permalink

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

Related Content

Installing SimpleSAMLphp Using Composer

Security Assertion Markup Language (SAML) is a standard that passes authentication credentials between hosts and essentially allows for a single sign on solution to be created. The standard uses XML files that get passed between the authentication system (known as the identity provider or IdP) and the service users want to sign into (known as the service provider or SP).

Create Checksums Using The Luhn Algorithm In PHP

The Luhn algorithm was created by Hans Peter Luhn and is a way of creating a simple checksum for a number. This algorithm, also known as the mod 10 algorithm, is used in a wide variety of applications but is commonly associated with credit card numbers.

If you look at the numbers on the front of your credit card the last digit on the right is the checksum. An algorithm is done on the other numbers and if the checksum is the same then the number is considered valid.

Swapping Between Different Composer Versions

I had an issue I was trying to debug today and needed a way to swap between different versions of composer. Composer is one of the few things that I install globally so it was locked at a particular version on the machine I was using. There has been some significant changes between version 1 and version 2 and it isn't quite safe to use a composer 2 package on a platform that has composer 1 installed. As some projects I'm working on haven't been upgraded yet I needed a way to swap between versions whilst this work was being done.

Creating A Game With PHP Part 4: Side Scrolling Shooter

As another step up from the game of snake I created in my last post I decided to try my hand at creating a side scrolling shooter. Just like my other posts, this is an ASCII based game played on the command line.

A side scrolling shooter, if you didn't already know, moves a scene from right to left across the screen with enemies moving with the scene towards the player's ship, which is on the left hand side of the scene. The player can fire bullets towards the enemies so remove them from the scene.

Seeding Random Numbers in PHP

Computers are not that great at creating random numbers as the methods they use are deterministic. That is, they start from a number (called a seed) and apply maths to that number to generate pseudorandom numbers. Most random numbers generated by computers programs use a seed provided by the system, which is generally the current time. If you can guess the initial value then you can start to work out what the random sequence of numbers generated is. Most random numbers, are therefore not suitable for encryption.

PHP: Find An Array Sequence In An Array

I was looking for a function that searched an array for another array, and after not finding one I decided to write it. What I was looking for was a function that took a smaller array and searched for that exact sequence of items in a larger array. As it happens, PHP does have a number of array search functions, but they didn't produce the correct result.