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