Sieve of Eratosthenes

The Sieve of Eratosthenes is a method for finding all the prime numbers starting with 2. It was created by Eratosthenes, a Greek mathematician who served as the head librarian at the famed Library of Alexandria.

This webpage takes the reader through the process of making a sieve to find the prime numbers between 1 and 100.

To start with, we list all the numbers that we want to look through for primes. In this case we are listing the numbers 1 through 100. This means we will find all primes up through 100. Since the number 1 is a special case, we leave the position for 1 blank.

cont01

The first number in the list is 2. This is the first prime number we will use. We will highlight 2 since it is prime, and shade all multiples of 2 since they are not prime.

How do we know that multiples of 2 are not prime?

cont02

We have now shaded all the multiples of 2 as an indication that they are not prime. The numbers that are not shaded are still candidates for prime numbers.

cont03

The next number in the list is 3. We now know that 3 is a prime number because it has not been shaded. This means it is not a multiple of any smaller integer.

cont04

Now we have shaded all multiples of 3. Note that any multiple of 3 that is also a multiple of 2 was shaded earlier.

cont05

Multiples of both 2 and 3 have been shaded. The next number in the list that has not been shaded is 5. This means that five is a prime number, since is it not a multiple of 2 or 3. How do we know that 4 is not a prime number?

cont06

Now we shaded all multiples of 5. Again, any multiples of 5 that are multiples of 2 or 3 have already been shaded.

cont07

Here, we can see that all multiples of 2, 3, and 5 have been shaded. Next we need to shade the multiples of 7.

cont08

Here, we can see that all multiples of 2, 3, 5, and 7 have been shaded. Look through the example and see if you can find any multiples of 11 to shade (11, 22, 33, etc.). There are none! Why? This is because we have already shaded 11*2, 11*3, 11*4, 11*5, 11*6, 11*7, 11*8, and 11*9. Since 11*11 = 121 is greater than 100, there will be no more multiples of 11 to shade.

If we did the Sieve of Eratosthenes for numbers up to 200, what would be the highest number we had to check for multiples?

cont09

The sieve is complete through 100. All the numbers that are not shaded are prime numbers.

cont10

Citation

Cite this source as:
McAdams, David, "The Sieve of Eratosthenes", from LifeIsAStoryProblem.org, 30 June 2007, URL http://www.lifeisastoryproblem.org/numbers/sieveeratosthenes.html

Other Resources

You can download a worksheet on the Sieve of Eratosthenes by clicking here: Download

cont11