5th July 2013 - 5 minutes read time
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.