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
Grammy Awards of 1976

... Country Instrumental Performance[?] Chet Atkins for "The Entertainer" Best Country Song Larry Butler[?] (songwriter) for "(Hey Won't You Play) Another Somebody ...