This post has already been read 3130 times!

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.

Algorithm descriptionA

prime numberis anatural numberwhich has exactlytwo distinct natural number divisors: 1 and itself.

Tofindall theprime numbersless than or equal to agiven integer nby Eratosthenes' method:

- Create a list of
consecutive integersfrom2 through n: (2, 3, 4, ..., n).- Initially, let
p equal 2, the first prime number.- Starting from p, enumerate its multiples by
counting to ninincrements of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).- Find the
first number greater than pin 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 markedareprime.The

main ideahere is that every value forpis 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.