The sieve of Eratosthenes is an easy to use algorithm for finding all prime numbers up to a certain limit. It is named after Eratosthenes of Cyrene, a Greek mathematician who lived in third century BC. In this post we illustrate the sieve of Eratosthenes in a series of diagrams.
The sieve identifies the prime numbers below a limit by eliminating all composite numbers below . The following describes the steps:
- Start with a listing of all positive integers .
- Select the number 2 and mark all multiples of 2 that are greater than 2 (in the diagrams below we use shading), essentially marking all even integers in the listing (except for 2).
- In each subsequent step, find the first number greater than the previously selected number. Then mark all multiples of that are greater than , i.e., marking .
- The process is stopped when multiples of have been marked for all integers .
The justification for in the above description is that any composite integer in the listing would have a prime divisor below . See the corollary at the end of the post.
The sieve of Eratosthenes is of course best done using using computer. We illustrate the process by finding all prime number below .
We start with Figure 1 which is a listing of all integers below 169.
Figure 1 – Positive Integers Below 169
Next, in Figure 2, we shade all multiples of 2 that are above 2. In other words we shade all even integers below 169 (excluding 2).
Figure 2 – Multiples of 2 are Shaded
The first number greater than 2 that has not been shaded is 3. In Figure 3 below, we shade all multiples of 3 that are greater than 3 and that have not been previously shaded (e.g. 9, 15, etc).
Figure 3 – Multiples of 3 are Shaded
The first number greater than 3 that has not been shaded is 5. In Figure 4 below, we shade all multiples of 5 that are greater than 5 and that have not been previously shaded.
Figure 4 – Multiples of 5 are Shaded
The first number greater than 5 that has not been shaded is 7. In Figure 5 below, we shade all multiples of 7 that are greater than 7 and that have not been previously shaded (e.g. 49, 77, 91, etc).
Figure 5 – Multiples of 7 are Shaded
The first number greater than 7 that has not been shaded is 11. In Figure 6 below, we shade all multiples of 11 that are greater than 11 and that have not been previously shaded. In this step, we only need to shade 121 and 143.
Figure 6 – Multiples of 11 are Shaded
The first number greater than 11 that has not been shaded is 13. In Figure 7 below, we shade all multiples of 13 that are greater than 13 and that have not been previously shaded. In this step, we only need to shade 169.
Figure 7 – Multiples of 13 are Shaded
By the time we finish with Figure 7, all multiples of have been shaded for all . So the remaining unshaded numbers are prime numbers. Note that for any integer in the above diagrams, if it is composite, it would have a prime divisor at or below 13 (see the corollary below).
Thus there are 39 prime numbers below 169 and they are:
2, 3, 5, 7,
11, 13, 17, 19,
41, 43, 47,
71, 73, 79,
101, 103, 107, 109,
131, 137, 139,
Why the Sieve Works
The marking or shading of multiples of numbers can stop at is justified by the following two lemmas.
Let be a composite integer greater than 1. Then has a divisor such that .
Since is composite, there are integers and such that with and . If one of and is , then we are done.
Suppose that both and . Then we have:
Thus one of and is .
Let be a composite integer greater than 1. Then has a prime divisor such that .
By Lemma 1, has a divisor such that . Since there can be only finitely many such divisors and since any finite set of real numbers has a least element, let be the smallest divisor of such that . Then must be a prime number. If not, by Lemma 1 would have a divisor with . This would mean is a divisor of contradicting the fact that is the smallest divisor of .
Because of these two lemmas, in checking whether a positive integer is a prime number, we only need to check for divisors . We have the following corollary, which is the basis of the sieve of Eratosthenes.
Let be any integer greater than 2. Any composite number in the following listing
has a prime factor .
Thus in the process for the sieve of Eratosthenes for identifying the prime numbers , we only need to eliminate the multiples of for all .