This post has already been read 3130 times!

220px-Eratosthene.01

In mathematics, the sieve of Eratosthenes, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

SieveofEratosthenes

Algorithm description

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.


To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

    1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
    2. Initially, let p equal 2, the first prime number.
    3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
    4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number(which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

The main idea here is that every value for p is prime, because we have already marked all the multiples of the numbers less than p. Note that some of the numbers being marked may have already been marked earlier (e.g. 15 will be marked both for 3 and 5).

As a refinement, it is sufficient to mark the numbers in step 3 starting from p2, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p2 is greater than n.

 

Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count in increments of 2p in step 3, thus marking only odd multiples of p. This actually appears in the original algorithm.This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds, i.e. numbers coprime with 2.

The PHP implementation of the Eratosthenes sieve isn’t difficult.

function eratosthenes_sieve(&$sieve, $n)
{
	$i = 2;

	while ($i <= $n) {
		if ($sieve[$i] == 0) {
			echo $i;

			$j = $i;
			while ($j <= $n) {
				$sieve[$j] = 1;
				$j += $i;
			}
		}
		$i++;
	}
}

$n = 100;
$sieve = array_fill(0, $n, 0);

// 2, 3, 5, 7, ..., 97
eratosthenes_sieve($sieve, $n);

 

Application

As I said prime numbers are widely used in cryptography, so they are always of a greater interest in computer science. In fact every number can be represented by the product of two prime numbers and that fact is used in cryptography as well. That’s because if we know that number, which is usually very very big, it is still very difficult to find out what are its prime multipliers.

Unfortunately the algorithms in this article are very basic and can be handy only if we work with small numbers or if our machines are tremendously powerful. Fortunately in practice there are more complex algorithms for finding prime numbers. Such are the sieves of Euler, Atkin and Sundaram.

Comments are closed.

Post Navigation