Exactly two factors
A prime number is a whole number with exactly two factors: 1 and itself. 7 is prime, because the only rectangle of 7 squares is one row, 1 × 7. 6 is not prime: it is 1 × 6 and also 2 × 3, so it has four factors.
A whole number with more than two factors is called a composite number. 6 is composite.
Cross out 1 first
To find every prime up to 100, write out the numbers from 1 to 100 in rows of ten. Cross out 1 first. Its only factor is 1, so it has one factor, not two, and it is not prime.
The numbers from 1 to 100, in rows of ten, with 1 crossed out.
Cross out the multiples
2 is the first number left, and it is prime: its only factors are 1 and 2. Keep 2, and cross out all the other multiples of 2: 4, 6, 8, and on up to 100. Each of those has 2 as a factor as well as 1 and itself, so it has more than two factors.
The next number not crossed out is 3. Nothing smaller than 3 divides it except 1, or it would already be crossed out, so 3 is prime. Keep 3, and cross out its other multiples: 9, 15, 21, and on. Some, like 6 and 12, are already crossed out.
4 is already crossed out, so the next prime is 5. Keep it, and cross out its multiples, which leaves 25, 35, 55, 65, 85 and 95 newly crossed out. Then keep 7 and cross out its multiples, which crosses out 49, 77 and 91 for the first time.
2 to 100, nothing struck yet: the sieve never tests a number for a factor, it only crosses out the multiples k × p
Strike the multiples of 2, 3, 5 and 7 and count what is left
Move the slider one step at a time. Each step crosses out the multiples of the next prime, 2, then 3, 5 and 7, and the count of numbers left goes down.
Why the sieve stops at 7
The next prime is 11, and it crosses out nothing new. A composite number up to 100 is a product of two smaller numbers, and the smaller of the two is 10 or less, because 11 × 11 = 121 is more than 100. Every number from 2 to 10 is 2, 3, 5 or 7, or a multiple of one of them, so every composite number up to 100 was crossed out already.
The numbers left are the primes. There are 25 of them: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
Three slips
Counting 1 as a prime. It has only one factor.
Crossing out the prime itself. Crossing out the multiples of 2 keeps 2: it is the only even prime.
Stopping too soon. 91 looks prime, but 91 = 7 × 13, so the multiples of 7 must be crossed out too.
Worked example: Primes: 60 Numbered Lockers Sorted by the Sieve, and the Rest Shared Equally
Question The 60 lockers in a school corridor are numbered 1 to 60. For Math Week, every locker with a prime number goes to a Primary 6 student. Locker 1 holds the first-aid kit. All the other lockers are shared equally among Primary 3, Primary 4 and Primary 5. (a) Use the Sieve of Eratosthenes to find how many lockers go to Primary 6 students. (b) How many lockers does each of the other three levels get?
1.Write 1 to 60 in rows of 10. Cross out 1: it is neither prime nor composite, and it is the first-aid locker.
Lockers 1 to 60 in rows of 10. Cross out 1: it is neither prime nor composite, and it holds the first-aid kit. 2.Keep 2 and cross out every other multiple of 2: 4, 6, 8, and so on up to 60. That crosses out 29 numbers.
Keep 2 and cross out its other multiples: 29 numbers. 3.Keep 3 and cross out the multiples of 3 that are still there: 9, 15, 21, 27, 33, 39, 45, 51 and 57. That is 9 more.
Keep 3 and cross out the multiples of 3 still there: 9, 15, 21, 27, 33, 39, 45, 51 and 57. 4.Keep 5 and cross out 25, 35 and 55; keep 7 and cross out 49. The next prime is 11, and 11 × 11 = 121 is more than 60, so every number left is prime.
Keep 5 and cross out 25, 35 and 55; keep 7 and cross out 49. Since 11 × 11 = 121 is more than 60, the sieve stops. 5.(a) The numbers left are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 and 59, so 17 lockers go to Primary 6 students.
(a) 17 numbers are left, and all of them are prime: 17 lockers go to Primary 6 students. 6.(b) The composite lockers are the ones crossed out after locker 1: 29 + 9 + 3 + 1 = 42, which is also 60 − 1 − 17. Shared among three levels, each gets 42 ÷ 3 = 14 lockers.
(b) 60 − 1 − 17 = 42 composite lockers, shared among three levels: 42 ÷ 3 = 14 each.
Answer: (a) 17 lockers; (b) 14 lockers each
Common mistakes
- Counting 1 as a prime. A prime has exactly two factors, 1 and itself, and 1 has only one factor, so it is not prime; here it is also the first-aid locker.
- Stopping the sieve after 5 and leaving 49 in the list. 49 = 7 × 7, so the multiples of 7 must be crossed out too; only once the next prime times itself passes 60 can the sieve stop.