Sieve of Eratosthenes

From Exampleproblems

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It is the predecessor to the modern Sieve of Atkin, which is faster but more complex. It was created by Eratosthenes, an ancient Greek mathematician. Wheel factorization is often applied on the list of integers to be checked for primality, before Sieve of Eratosthenes is used, to increase the speed.

Algorithm

Image:Animation Sieb des Eratosthenes.gif

First, write three things :

The highest factor to check for. It is the square root of the last number you care about, rounded down.
A list of primes you've found. It starts empty.
A list of numbers that remain to be checked. It starts out filled with all integers from two up to the last number you care about.

Then, repeat the following until you've checked all you need :

Remove the first remaining number to the primes list.
Delete anything that's a multiple of the number you just removed.

Finally, remove all remaining numbers to the primes list.

Example :

Highest to check =  = 3
Primes = []
Remaining = [2, 3, 4, 5, 6, 7, 8, 9, 10]

(After the first iteration, two has been moved to the primes and
multiples of two (4, 6, 8, 10) have been deleted)

Primes = [2]
Remaining = [3, 5, 7, 9]
3 > Highest to check ?  No.

Primes = [2, 3]
Remaining = [5, 7]
5 > Highest to check ?  Yes; we're done checking.

Primes = [2, 3, 5, 7]
Remaining = []

We can see that the primes up to ten are 2, 3, 5, and 7.

Reference

Κοσκινον Ερατοσθενους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.

For more advanced developments, see: