The sieve of Eratosthenes is an algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number 
you wish to include in the table. Cross out all numbers 
which are divisible by 2 (every
second number). Find the smallest remaining number 
. It is 3. So cross out all numbers 
which are divisible by 3 (every third number). Find the
smallest remaining number 
. It is 5. So cross out all numbers 
which are divisible by 5 (every fifth number).
Continue until you have crossed out all numbers divisible by 
, where 
is the floor function.
The numbers remaining are prime. This procedure is
illustrated in the above diagram which sieves up to 50, and therefore crosses out
composite numbers up to 
. If the procedure is then continued up to 
, then the number of cross-outs gives
the number of distinct prime factors of
each number.
The sieve of Eratosthenes can be used to compute the prime counting function as
 |
which is essentially an application of the inclusion-exclusion principle (Havil 2003, pp. 171-172).
Nicomachus preserved an ancient account of the sieve in Book I, Chapter 13 of his Introduction to Arithmetic (Nicomachus 1926). The table above, from an Arabic translation in British Library Add MS 7473, illustrates the transmission of this Greek method through the Arabic manuscript tradition (British Library).
