Sieve of Eratosthenes

The sieve of Eratosthenes is an algorithm for making tables of primes. Sequentially write down the integers from 2 to an integer . Starting with 2, take the remaining primes in increasing order and cross out all multiples of greater than . For example, when sieving up to 50, first cross out all numbers greater than 2 that are divisible by 2 (every second number). The next remaining number is 3, so cross out all numbers greater than 3 that are divisible by 3 (every third number). The next remaining number is 5, so cross out all numbers greater than 5 that are divisible by 5 (every fifth number).

The numbers remaining after sieving with primes at most are prime. The diagram above sieves up to 50 using primes at most , where is the floor function. If instead each multiple of every prime up to is marked, including each prime itself and counting repeated markings, then the number of markings gives the number of distinct prime factors of each number.

The sieve of Eratosthenes can be used to compute the prime counting function . For a real number , let be the product of all primes , with when there are none. The inclusion-exclusion principle gives

where is the Möbius function (Havil 2003, pp. 171-172; Oliveira e Silva 2006, pp. 760-761). The sum counts 1 together with the primes greater than and at most .

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).