## The Sieve of Eratosthenes | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

ex01
ex02
ex03
ex04
ex05
ex06
ex07
ex09
ex09
ex10
ex11 |
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
## CitationCite this source as:
## Other ResourcesYou can download a worksheet on the Sieve of Eratosthenes by clicking here: Download cont11
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||