Math 6

The sieve of Eratosthenes

You want every prime up to 120. Is there a way to find them all at once, without testing each number on its own?

You need

Prime and composite numbersGrade 4

Where you are 10 in Divisibility and primes

Number9

Divisibility and primes10

▴ 5 above Prime factorization Tests for three and nine

The sieve of Eratosthenes

Every number has exactly one prime factorization Greatest common factor and least common multiple4

When you reach for it

At the lantern festival, 120 lanterns hang in a long row, numbered 1 to 120. The plan is to leave lit only the lanterns whose numbers are prime and to put the rest out, in rounds. Testing each number on its own would work, but slowly: to decide whether 119 is prime by itself you try divisor after divisor.

Recall from Prime and composite numbers that a prime is a whole number greater than 1 with exactly two factors, 1 and itself, and a composite number is a whole number greater than 1 with more than two. The sieve of Eratosthenes, a method that carries his name, finds every prime up to a chosen number in one sweep. Instead of asking “what divides this number?” over and over, it asks “which numbers does this prime divide?”, and those it can list by counting up in steps. A hard question asked many times becomes an easy one asked a few times.

Reach for it when you want all the primes in a range: to make a table, to see how the primes are spaced, or to have the small primes ready for prime factorization. To test a single number, the same idea works in a smaller form (Example 3).

The procedure

Running the rounds

Write 1 to 120 on a board, ten to a row. Every lantern starts lit.

Put out 1. It is not prime, for the reasons at the end of this section.

Round 2. The first lit number is 2. Circle it: no whole number other than 1 and 2 can divide 2, so it is prime. Now cross out every multiple of 2 after 2 itself: 4, 6, 8, \ldots, 120. Each has 2 as a factor besides 1 and itself, so each is composite. That is 59 lanterns.

Round 3. The next lit number is 3. Circle it and cross out its multiples. The even ones are out already, so the new ones are 9, 15, 21, \ldots, 117, going up in sixes: 19 lanterns.

Round 5. The next lit number is 5, since 4 went out in round 2. Circle it. The multiples of 5 still lit are 25, 35, 55, 65, 85, 95, 115: seven lanterns.

Round 7. Circle 7. Only 49, 77, 91, 119 are new.

Stop. The next lit number is 11, and 11 \times 11 = 121 is past the end of the board. Every lantern still lit is prime, so circle them all.

Figure 1The board after the rounds for 2, 3, 5 and 7. The circled lanterns are the 30 primes up to 120.

That is 1 lantern at the start and 59 + 19 + 7 + 4 = 89 in the rounds, 90 in all, which leaves 120 - 90 = 30 primes:

\begin{aligned} &2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \\ &31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \\ &73, 79, 83, 89, 97, 101, 103, 107, 109, 113 \end{aligned}

Four facts make every step safe.

Why the next lit number is always prime

Suppose a number n is still lit when a round ends, so no smaller prime divides it. If n were composite it would have factors between 1 and n; take the smallest, d. Then d is prime, because anything else dividing d would also divide n and be a smaller factor than d. So n would have a prime factor smaller than itself, and that prime’s round would have put n out. It did not, so n is prime.

The argument shows something used all through this lesson: a composite number’s smallest factor greater than 1 is a prime, and since the rounds go in order, that prime’s round is the one that puts the number out.

Why a round can start at p \times p

In round 7, the multiples 14, 21, 28, 35, 42 were already out. That is no accident. A multiple of a prime p below p \times p is k \times p with k between 2 and p - 1. The smallest factor of k greater than 1 is a prime smaller than p, and k \times p is a multiple of it too, so that earlier round already put it out. The first new lantern in round p is p \times p.

Why you can stop when p \times p passes the end

Take any composite n on the board, written as n = a \times b with a and b both greater than 1 and a the smaller (or equal) one. Then

a \times a \le a \times b = n \le 120

Since 11 \times 11 = 121, a is at most 10. So n has a factor from 2 to 10, which makes its smallest factor greater than 1 a prime no bigger than 10: one of 2, 3, 5, 7. Those four rounds put out every composite number on the board.

In general, on a board that ends at N, run a round for each prime p with p \times p \le N and stop at the first prime with p \times p > N. Later courses say this as “stop at the square root of N”, the number which times itself makes N.

Why 1 is not prime

A prime has exactly two factors. The number 1 has only one, itself, so it is not prime; it is not composite either. The sieve shows why the line is drawn there. If 1 counted as a prime, its round would cross out every multiple of 1, which is every number, and the board would go dark. The arguments above also lean on “the smallest factor greater than 1”: every number has 1 as a factor, so 1 says nothing about which numbers are composite. And with 1 left out, each number breaks into primes in only one way, which Every number has exactly one prime factorization proves; with it, 6 = 2 \times 3 could also be written 1 \times 2 \times 3.

Worked examples

Example 1

How many rounds a board needs

Nadia, Emeka and Ingrid each make their own board. Which rounds does each need?

(a) 1 to 50 \qquad (b) 1 to 200 \qquad (c) 1 to 1000

Solution

A round is needed for each prime p with p \times p no bigger than the last number.

(a) 7 \times 7 = 49 \le 50, but 11 \times 11 = 121 > 50. Rounds 2, 3, 5, 7. Round 7 puts out only 49, since 7 \times 11 = 77 is off the board.

(b) 13 \times 13 = 169 \le 200, but 17 \times 17 = 289 > 200. Rounds 2, 3, 5, 7, 11, 13: six rounds.

(c) 31 \times 31 = 961 \le 1000, but 37 \times 37 = 1369 > 1000. Rounds 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31: eleven rounds for a thousand lanterns.

Example 2

Which round puts a lantern out

Jun runs the 120 board. Which round puts out each lantern?

(a) 87 \qquad (b) 91 \qquad (c) 115 \qquad (d) 100

Solution

A lantern goes out in the round of its smallest prime factor, so try 2, then 3, then 5, then 7.

(a) 87 is odd. Its digit sum is 8 + 7 = 15, a multiple of 3, so by the test for 3, 3 divides it: 87 = 3 \times 29. Round 3.

(b) 91 is odd, its digit sum 10 is not a multiple of 3, and it does not end in 0 or 5. But 91 = 7 \times 13. Round 7. It looks prime and is not; counting up in sevens lands on it anyway.

(d) 100 is even. Round 2. Round 5 reaches 100 as well, but it is already out. A lantern goes out once, in the first round that reaches it.

Example 3

Testing one number

Is Emeka’s number 113 prime? Is Rohan’s number 143?

Solution

Only primes with p \times p no bigger than the number need testing, by the stopping argument applied to that number alone.

For 113: 11 \times 11 = 121 > 113, so try 2, 3, 5, 7. It is odd, its digit sum is 5, it does not end in 0 or 5, and 7 \times 16 = 112 leaves remainder 1. So 113 is prime.

For 143: 11 \times 11 = 121 \le 143 but 13 \times 13 = 169 > 143, so try 2, 3, 5, 7, 11. The first four fail (7 \times 20 = 140 leaves remainder 3), and 11 \times 13 = 143. So 143 is composite. Stopping at 7 here would have been wrong.

Example 4

Extending the board to 150

Ingrid hangs lanterns 121 to 150. Which of them are prime?

Solution

11 \times 11 = 121 \le 150 and 13 \times 13 = 169 > 150, so the rounds are 2, 3, 5, 7, 11.

Round 2 leaves the fifteen odd numbers 121, 123, \ldots, 149.

Round 3 puts out 123, 129, 135, 141, 147 (the odd multiples of 3 go up in sixes).

Round 5 puts out 125 and 145; 135 is already out.

Round 7 puts out 133 = 7 \times 19; the next odd multiple, 147, is already out.

Round 11 puts out 121 = 11 \times 11 and 143 = 11 \times 13.

The primes left are 127, 131, 137, 139, 149. Round 11 did nothing on the old board but is needed here: 121 and 143 have no prime factor smaller than 11.

Example 5

Gaps between primes

Saoirse looks at the 30 circled lanterns on the 120 board. (a) Which circled lanterns are two apart? (b) What is the longest run of dark lanterns between two circled ones?

Solution

The gap between two primes that are next to each other in the list is the larger minus the smaller. Two primes with a gap of 2, such as 11 and 13, are twin primes.

(a) Reading along the list, the pairs two apart are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103) and (107, 109). Ten pairs.

(b) The largest gap is 8, from 89 to 97, so the seven lanterns 90 to 96 are all dark.

Every gap except the first, from 2 to 3, is even: after 2 every prime is odd, because round 2 put out every even number except 2, and an odd number minus an odd number is even. Whether twin primes go on for ever is not known; the claim that they do is called the twin prime conjecture, and it has not been proved.

Example 6

Making a long dark stretch

Without running a sieve, find five whole numbers in a row that are all composite.

Solution

Take 2 \times 3 \times 4 \times 5 \times 6 = 720, a multiple of each of 2, 3, 4, 5, 6. Then 722 = 720 + 2 is a multiple of 2, since adding two multiples of 2 gives a multiple of 2. In the same way 723 is a multiple of 3, 724 of 4, 725 of 5 and 726 of 6. Each is larger than the number that divides it, so all five, 722 to 726, are composite.

Multiplying 2 through 11 instead gives ten in a row, and so on, so the gaps between primes can be as long as you like. The primes thin out, but they never stop: that is There are infinitely many primes.

Boundaries

The sieve needs an end. It finds the primes up to a chosen number N. To go further, extend the board and run the rounds again on the new part, adding a round each time N passes the next p \times p, as in Example 4.

It starts at 2. The numbers 0 and 1 are neither prime nor composite, so 1 is put out before the rounds begin and 0 is not on the board.

Only primes get a round. There is no round for 4 or 9: every multiple of 4 is a multiple of 2, and every multiple of 9 a multiple of 3, so those lanterns are already out.

It lists primes; it does not break numbers into them. The round that puts a number out names its smallest prime factor, and that is all. Writing a number as a product of primes is Prime factorization.

For one large number, skip the board. Test only the primes p with p \times p no bigger than the number, as in Example 3.

Where this goes next

The primes on the board are the building blocks of every whole number above 1. Next, prime factorization splits a number into them, and Every number has exactly one prime factorization shows the split is always the same. Those splits are the quickest route to the greatest common factor and least common multiple. And the question the gaps raise, whether the primes ever run out, is answered by There are infinitely many primes.

Exercises

Running the sieve

Run the sieve on 1 to 40. Which rounds does it need, and which numbers are prime?
Which rounds does a board from 1 to 90 need?
Which rounds does a board from 1 to 300 need?
On a board from 1 to 200, which lanterns does the round for 7 put out for the first time?
On a board from 1 to 200, which lanterns does the round for 13 put out for the first time?

Which round puts it out

On the 120 board, which round puts out each lantern? (a) 117 (b) 85 (c) 77 (d) 111 (e) 98

Prime or not

Decide whether each number is prime, and say which primes you had to test.

101
133
169
157
Saoirse says 119 must be prime: it is odd, its digit sum is not a multiple of 3, and it does not end in 0 or 5. Is she right?

Beyond the board

Find the primes from 151 to 170. Which rounds do you need?
The primes between 120 and 200 are 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199. List the twin prime pairs among them, and find the largest gap.
120 = 2 \times 3 \times 4 \times 5, and 120 is also a multiple of 6. Use this to show that 122, 123, 124, 125, 126 are all composite.
Jun runs the sieve on 1 to 60. After 1 is put out and the rounds for 2 and 3, how many lanterns are still lit? Which lanterns do the rounds for 5 and 7 then put out, and how many primes are left?

Reasoning

Give two reasons why 1 is not counted as a prime.
Explain why, in round 7, the lanterns 14, 21, 28, 35, 42 are already out.
Explain why the sieve never needs a round for 4 or for 9.
Explain why every lantern still lit after round 7 on the 120 board is prime, even though there were no rounds for 11, 13 and the rest.
Look at the board in rows of six. Explain why, after the rounds for 2 and 3, every lit number other than 2 and 3 is one more or one less than a multiple of 6.

Figure 2Rows of six after the rounds for 2 and 3. Apart from 2 and 3, only the first and fifth columns are still lit.

Explain why 2 and 3 are the only primes that are next to each other, and why every other gap between primes next to each other in the list is even.

Answers

Rounds 2, 3, 5, since 5 \times 5 = 25 \le 40 and 7 \times 7 = 49 > 40. The primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, twelve in all.
Rounds 2, 3, 5, 7. 7 \times 7 = 49 \le 90 and 11 \times 11 = 121 > 90.
Rounds 2, 3, 5, 7, 11, 13, 17. 17 \times 17 = 289 \le 300 and 19 \times 19 = 361 > 300.
49, 77, 91, 119, 133, 161. Each new one is 7 \times k with k from 7 to 28 (since 7 \times 29 = 203 is off the board) and k having no factor 2, 3 or 5: k = 7, 11, 13, 17, 19, 23. For example 175 = 7 \times 25 went out in round 5.
Only 169. It starts at 13 \times 13 = 169; the next multiples, 182 (even) and 195 (a multiple of 3), are already out, and 208 is off the board.
(a) Round 3: digit sum 9, 117 = 3 \times 39. (b) Round 5: odd, digit sum 13, ends in 5. (c) Round 7: 77 = 7 \times 11. (d) Round 3: digit sum 3, 111 = 3 \times 37. (e) Round 2: 98 is even.
Prime. Test 2, 3, 5, 7, since 11 \times 11 = 121 > 101: it is odd, digit sum 2, ends in 1, and 7 \times 14 = 98 leaves remainder 3.
Composite: 133 = 7 \times 19. Testing 2, 3, 5 fails, then 7 divides it.
Composite: 169 = 13 \times 13. Since 13 \times 13 \le 169, you must test up to 13; the primes 2, 3, 5, 7, 11 all fail and 13 divides it.
Prime. Test 2, 3, 5, 7, 11, since 13 \times 13 = 169 > 157: odd, digit sum 13, ends in 7, and 7 \times 22 = 154 and 11 \times 14 = 154 both leave remainder 3.
No: 119 = 7 \times 17. Her checks rule out only 2, 3 and 5; round 7 puts 119 out.
151, 157, 163, 167. Rounds 2, 3, 5, 7, 11, 13, since 13 \times 13 = 169 \le 170. Of the odd numbers, 153, 159 and 165 are multiples of 3, 155 of 5, 161 = 7 \times 23 and 169 = 13 \times 13.
Five twin pairs: (137, 139), (149, 151), (179, 181), (191, 193), (197, 199). The largest gap is 10, twice: 139 to 149 and 181 to 191.
122 = 2 \times 61, 123 = 3 \times 41, 124 = 4 \times 31, 125 = 5 \times 25, 126 = 6 \times 21. Since 120 is a multiple of k for each k from 2 to 6, so is 120 + k, and 120 + k is bigger than k.
21 lit: 2, 3 and the nineteen numbers 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59. Round 5 puts out 25, 35, 55 and round 7 puts out 49, leaving 17 primes.
1 has only one factor, and a prime needs exactly two. And if 1 had a round, it would cross out every number, since every number is a multiple of 1.
Each is k \times 7 with k from 2 to 6, so it is also a multiple of a prime smaller than 7: 14, 28, 42 went out in round 2, 21 in round 3, 35 in round 5.
Every multiple of 4 is a multiple of 2, and every multiple of 9 a multiple of 3, so they are all out before those numbers come up. Also 4 and 9 are out themselves, so the sieve never stops on them.
A composite n \le 120 can be written a \times b with a \le b, so a \times a \le 120 and a \le 10. Its smallest factor greater than 1 is then a prime no bigger than 10, that is 2, 3, 5 or 7, and that round put it out.
Each column holds numbers of one form 6r + c. Columns 2, 4 and 6 are even, and columns 3 and 6 are multiples of 3, so only columns 1 and 5 survive. Those numbers are 6r + 1, one more than a multiple of 6, and 6r + 5 = 6(r + 1) - 1, one less than one.
Of two whole numbers next to each other, one is even, and the only even prime is 2; so the pair must include 2, and 1 is not prime, which leaves 2 and 3. After 2, every prime is odd, and the difference of two odd numbers is even.