ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

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

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.