Encyclopedia > Sieve of Eratosthenes

Article Content

Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple algorithm for finding all the prime numbers up to a specified integer.

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 any number which is a multiple of the number you just added to the known primes list.

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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Courts of the United Kingdom ... still sit frequently: Coroners Courts - The post of Coroner is ancient, dating from the 11th Century, and coroners still sit today to determine the cause of death in ...