Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple method for finding all the prime numbers up to a specified integer. For an example, I will use the integers 1 to 15.

Step 1. Write your list of integers.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Step 2. Eliminate the number 1 from the list.

2 3 4 5 6 7 8 9 10 11 12 13 14 15

Step 3. 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

Step 4. Go to the Main List and eliminate any number which is a multiple of the last number in the Known Primes list.

Known primes: 2
Main list: 3 5 7 9 11 13 15

Step 5. If the biggest number in the Main List is less than the square of the biggest number in the Known Prime list, mark all numbers in the Main List as prime; otherwise, return to Step 3.

15 is greater than the square of 2.

Returning to Step 3:

Known primes: 2 3
Main list: 5 7 9 11 13 15

Step 4:

Known primes: 2 3
Main list: 5 7 11 13

13 is greater than the square of 3.

returning to step 3:

Known primes: 2 3 5
Main list: 7 11 13

Step 4: (no changes to either list)

5 is greater than the square of 13.

RESULT: The primes in the range 1 to 15 are: 2, 3, 5, 7, 11, 13.