The sieve of Eratosthenes: finding primes by removing multiples

0:00Here are the numbers from one to one hundred. I'm going to find every single prime in this grid, and I am not going to do one division. Not one. I'm not even going to check whether any number is prime. All I'm going to do is cross things out. Before I start, guess. How many of these hundred numbers will still be standing at the end? Pick a number and hold on to it. Most people guess far too high.

0:30The first move is a strange one. We remove the number one. Not because it's composite. It isn't. One has exactly one factor, so it's neither prime nor composite. It sits outside both classes. So it comes off the board straight away, and we never think about it again. Ninety-nine numbers left. Now the real work. Circle two. Two stays. We circle it, and we do not cross it out, even though two is a multiple of two.

1:04That's the mistake almost everyone makes. A number circles first, and only its later multiples get struck. If you cross out two as well, you'll delete every prime on the board. So. Circle two, then strike every multiple of two after it. Four, six, eight, ten, twelve, and on and on, all the way to one hundred. Half the grid is gone in a single pass. Now find the next number that is still untouched. It's three.

1:36Circle it, and strike its later multiples. Six, nine, twelve, fifteen, eighteen. Notice something. Six was already gone. Twelve was already gone. We just skip over them. A number can be struck twice, and it makes no difference. Next untouched number. Four is gone, so it's five. Circle five. Strike ten, fifteen, twenty, twenty-five, and the rest. Then seven. Circle it, strike fourteen, twenty-one, twenty-eight, thirty-five, forty-nine. Notice that forty-nine is the first multiple of seven that wasn't already crossed out.

2:19Now, the obvious objection is exactly the right one to make. This can't just be magic. There has to be a reason it works. There is, and it comes in two halves. Here's the first. Why does the next untouched number always turn out to be prime? Think about what has already happened. Every prime smaller than it has had a turn. And on its turn, it struck out all of its own multiples.

2:48So if any of those smaller primes divided our number, our number would already be crossed out. It isn't. So no smaller prime divides it. And any number with a factor bigger than one has a prime factor. So it has no factors except one and itself. It's prime. Guaranteed. Now the second half. Why can't a composite number sneak through? Take any composite number. Look at its smallest factor apart from one.

3:20That smallest factor has to be prime. Here's why. If it had a factor of its own, that would be an even smaller factor of our composite number. But we picked the smallest. So the smallest factor is prime. Which means it got circled, and it got a turn. And on that turn, our composite number was struck, because it's one of that prime's multiples. No composite escapes. Every one of them has a prime waiting to delete it.

3:52Those two arguments together are the whole reason the sieve works. Nothing was tested. Everything was accounted for. So when do we stop? The next uncrossed number after seven is eleven. Let's run its pass and watch what happens. Twenty-two. Already gone, struck as a multiple of two. Thirty-three. Gone, as a multiple of three. Forty-four, gone. Fifty-five, gone as a multiple of five. Sixty-six, seventy-seven, eighty-eight, ninety-nine. Every single one already crossed out.

4:32The pass for eleven deletes nothing new, and neither does any pass after it. Here's why. Eleven times eleven is one hundred and twenty-one, which is off our grid. So any multiple of eleven that fits on this grid has to be eleven times something smaller than eleven, and that smaller thing already had its turn. Seven was the last pass that mattered, because seven times seven is forty-nine, and that still fits.

5:04And we're done. Look at the board. Every number is either circled or crossed out, and we never divided anything. The circles are the primes. There are twenty-five of them below one hundred. Two, three, five, seven, eleven, thirteen, seventeen, nineteen, twenty-three, twenty-nine. Thirty-one, thirty-seven, forty-one, forty-three, forty-seven, fifty-three, fifty-nine, sixty-one, sixty-seven. Seventy-one, seventy-three, seventy-nine, eighty-three, eighty-nine, and ninety-seven. The crosses, apart from the one we removed at the start, are the composites.

5:46How close was your guess? Twenty-five out of a hundred. A quarter of them. Now the grid is finished, it's worth reading it like a picture. First question. Is there any even number in the circles apart from two? No, and there never could be. Every other even number was struck on the very first pass. Second question. How far apart are neighbouring primes? The closest pair is two and three, sitting right next to each other with a gap of one.

6:20That happens exactly once, and it has to, because after two, every prime is odd. The biggest gap below one hundred is between eighty-nine and ninety-seven. Seven numbers in a row with nothing circled. Third question. Does every row of ten hold the same number of primes? Not at all. The first two rows have four each. The last row, ninety-one to one hundred, has just one. Ninety-seven, alone. That last row points at something. The primes thin out as you climb.

6:58And you can find stretches with no primes at all. Look for seven composite numbers in a row, somewhere on this grid. Pause and hunt for it if you like. The finished grid makes it a matter of looking, not calculating. There's exactly one such run below one hundred. Ninety to ninety-six. Ninety, ninety-one, ninety-two, ninety-three, ninety-four, ninety-five, ninety-six. Seven in a row, not a prime among them. And ninety-one is the sneaky one. It looks prime. It's seven times thirteen.

7:36While we're reading the grid, look for the ringed pairs with exactly one cross between them. Three and five. Five and seven. Eleven and thirteen. Those are the twin primes, and there are eight such pairs below one hundred. This method has a name and an owner. It's called the sieve of Eratosthenes, after a Greek mathematician who lived about two thousand two hundred years ago. A sieve is the kitchen tool you shake to let the small stuff fall through and keep what you want.

8:12That's exactly what this is. The composites fall through the holes, and the primes are what's left in the pan. And nothing about it stops at one hundred. Run the same procedure on a thousand numbers, or a million. The rule never changes. The only thing that changes is how far you have to go before the passes stop paying. So here's what the sieve gave us, and here's what it didn't.

8:42It gave us every prime below one hundred, without testing a single number. The primes are simply whatever the crossing-out failed to reach. They're defined by what didn't happen to them. But there's one thing the sieve can never tell us. We watched the primes get rarer. Four in the first row, one in the last. So does the thinning ever finish? Is there a last prime, a biggest one, with nothing but composites after it?

9:12Running a bigger sieve can't answer that. You'd be running forever, and never knowing. That question needs a different kind of argument altogether, and a Greek mathematician called Euclid found it. What's your instinct? Do the primes run out, or go on forever? Tell me in the comments before we settle it.