Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is a simple algorithm for finding all the prime numbers up to a specified integer. You start with a list of all integers beginning with 2 and at every step, you remove the smallest number (which is a prime) and all multiples of this number (which are composite).

In more detail, the algorithm goes as follows

Step 1. List the integers, starting with "2".

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Step 2. Mark the first number in the list as prime.

Known primes: 2

Main list: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Step 3. Step through the main list eliminating all multiples of the number just added to the list of known primes.

Known primes: 2

Main list: 3 5 7 9 11 13 15 17 19

Step 4. If the largest number in the main list is less than the square of the largest number in the known prime list, mark all numbers in the main list as prime; otherwise, return to Step 2.

Since 19 is greater than the square of 2 (4), we return to Step 2:

Known primes: 2 3

Main list: 5 7 9 11 13 15 17 19

Then step 3:

Known primes: 2 3

Main list: 5 7 11 13 17 19

19 is greater than the square of 3 (9), so we return to step 2:

Known primes: 2 3 5

Main list: 7 11 13 17 19

Then step 3 (no changes to either list).

19 is less than the square of 5 (25), so the remaining list is prime.

RESULT: The primes in the range 2 to 20 are: 2, 3, 5, 7, 11, 13, 17, 19.

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:

External link

Interactive animation (JavaScript required)