The primes are what is left over

There is no procedure that produces the primes. There is a procedure that produces everything else, and the primes are the residue.

The procedure is about twenty-two centuries old and is attributed to Eratosthenes of Cyrene, the librarian at Alexandria who also measured the Earth. Circle two, and cross out every second number after it. Circle the next survivor, three, and cross out every third number after it. Continue. Whatever is never crossed out is prime.

The method is so simple that its oddness is easy to miss. Nothing in it ever asks whether a number is prime. It asks, repeatedly, whether a number is a multiple of something already known — and primality is what remains when that question has been asked often enough. The definition of a prime is a statement about absence: divisible by nothing except itself and one. The sieve is that absence made mechanical, and the mechanism has no notion at all of the objects it produces.

That is the pattern the whole subject inherits. Almost every elementary fact about the primes is arrived at by ruling things out, and almost every difficulty in the subject is the difficulty of proving a negative.

The attribution is worth a sentence, because it is unusually thin. No writing of Eratosthenes’ survives that describes the method; it comes down through Nicomachus of Gerasa, writing some three centuries later, who names him. What Eratosthenes is otherwise remembered for — measuring the circumference of the Earth from the difference between two noon shadows — has the same character as the sieve: an exact result extracted from an arrangement simple enough to hold in the head. The word sieve is Nicomachus’s, and it is the right one. A sieve is defined by what falls through it.

One striker each #

Watching a single pass turns up something worth keeping.

The second pass strikes multiples of three. But half of those — six, twelve, eighteen — have already gone, struck by two. A sieve implemented naively visits them a second time and crosses out a cell that carries a line already.

The colouring in the second figure removes the waste, and it does so by leaning on a fact rather than on a trick. Each composite is coloured by its smallest prime factor — the one prime that gets to it first — and every struck cell therefore carries exactly one colour. That is a claim about factorisation dressed as a claim about the drawing: every composite has a smallest prime factor, and it has only one, so the work can be arranged so that nothing is struck twice.

Two consequences follow immediately, and together they turn a demonstration into a genuine algorithm. Striking multiples of $p$ can begin at $p^2$, because every smaller multiple of $p$ carries a smaller factor and has gone already. And the passes can stop once $p^2$ exceeds the limit, because a composite below $n$ must have a factor at or below $\sqrt{n}$. Four passes settle the first hundred numbers. Ten settle the first thousand. Sixty-five settle the first hundred thousand.

The claim underneath both of them deserves to be looked at rather than assumed.

If a composite could be built from two genuinely different sets of primes, “the smallest prime factor” would not name anything, the colouring would be arbitrary, and the optimisation above would be wrong. It is not wrong, but the reason it is not wrong is a theorem rather than an observation, and it is the subject of its own essay.

The wheel, and where the speed-ups stall #

The starting-at-$p^2$ trick is the first of a family, and following the family a little way says something about the whole subject.

The next member is the wheel. Multiples of two can be skipped by stepping through the odd numbers alone, which halves the work; skipping multiples of two and three as well leaves only the numbers congruent to $1$ or $5$ modulo $6$, which is a third of them; adding five leaves eight residues out of thirty, which is $26.7\%$. Every prime added to the wheel cuts the survivors by a factor $1 - 1/p$, and each factor is closer to one than the last.

So the returns diminish, and they diminish at a rate that is already familiar. The product of $(1 - 1/p)$ over the wheel’s primes is the same product that appeared in the density estimate above, and it shrinks like $1/\log$ of the largest prime in the wheel. Doubling the effort spent on the wheel buys a vanishing improvement, and in practice nobody goes past the wheel on $2, 3, 5, 7$.

The shape of that argument is worth keeping. A quantity that governs how expensive the sieve is to run turns out to be the same quantity that governs how many primes there are — because both are asking, in different words, what fraction of the numbers a set of small primes can account for.

What the sieve costs #

Counting the strikes prices the whole procedure. The multiples of $p$ below $n$ number about $n/p$, so the total work is roughly

$$n \sum_{p \le \sqrt{n}} \frac{1}{p},$$

and the sum of the reciprocals of the primes grows like $\log \log n$ — a function so slow that for every range anybody will actually sieve it behaves as a small constant. Sieving to a million costs about three operations per number. Sieving to a billion costs about four. The sieve is very nearly linear in the size of the range, and after two millennia it is still the fastest known way to produce every prime below a bound.

It has one cost that is not measured in operations, and it is the more interesting of the two. The sieve requires the whole range to be in front of it at once. There is no way to run it on a single number: asking whether one given number is prime, without producing every prime below it, is a different problem with different machinery, and that difference is the reason a modern primality test looks nothing at all like the figures above. Eratosthenes’ method is an instrument for populations of numbers rather than for individuals, and almost every use it is put to today — building tables of small primes to feed other algorithms — is a population use.

There is a memory cost too, and it eventually bites. Sieving to $n$ needs $n$ bits. Sieving a range near a very large number can be done in segments, which the segmented sieve does, but even a segmented sieve needs every prime up to $\sqrt{n}$, and past a certain size those cannot be stored on any machine. The instrument has a range. It is generous rather than unlimited.

The count, and the shape it takes #

Once every prime below a bound is on the table they can be counted, and counting them is where the subject stops being about individual numbers. Write $\pi(x)$ for the number of primes up to $x$.

The dashed curve is what a density argument gives, and the argument is worth following, because it is nearly right and entirely heuristic. Of the numbers up to $x$, a fraction $\tfrac12$ survive the first pass; a fraction $\tfrac23$ of those survive the second; then $\tfrac45$, then $\tfrac67$. Treating the passes as independent, the surviving fraction is

$$\prod_{p \le \sqrt{x}} \left(1 - \frac{1}{p}\right),$$

which Mertens showed behaves like $2e^{-\gamma}/\log x$.

Independence is a lie. Being a non-multiple of three is not independent of being odd, and the two conditions interfere in a way the product ignores. What is worth noticing is the size of the lie: it costs a constant factor and leaves the shape intact. The true statement — the prime number theorem, proved in 1896 by Hadamard and de la Vallée Poussin working separately — is that $\pi(x)$ really does behave like $x/\log x$, and the constant the heuristic gets wrong is exactly the one the theorem gets right.

So the staircase is a picture of density, and density is what the sieve is actually about. A number near $x$ has, in the loosest sense that can be made precise, a chance of about $1/\log x$ of being prime. The primes thin out; they thin out extremely slowly; and the rate at which they thin out is a property of the logarithm, which had no business appearing in a question about divisibility at all.

What the picture cannot show #

The staircase looks smooth at this scale. It is not, and no drawing at any scale anyone can look at will show what its irregularity is like.

The bars refuse to settle down. Gaps of exactly two — twin primes — keep appearing as far as anyone has looked, and whether they keep appearing forever is unknown. Arbitrarily long stretches with no prime at all exist, by the factorial construction in the caption, which is one of the very few completely elementary arguments in this subject that says something about the far distance.

The sieve is silent about all of it. Running it further produces more data and no more understanding, and that is the specific frustration of this field: the objects are concrete, the computations are easy, and the questions have resisted for centuries. The pattern in the primes on a spiral is the same silence seen from another angle — an unmistakable visual structure, reproducible on any grid anybody cares to draw, with no proof attached to any part of it.

There is a subtler thing the figures cannot show. Every drawing here is of a beginning, and the beginning of the number line is unrepresentative in a way that has misled people repeatedly. Below a hundred the primes are dense enough to look almost regular. The behaviour the theorems describe is asymptotic, and the first few thousand numbers are not a sample of the numbers — a lesson that this collection has run into from several different directions.

Two ways to count the same crossings #

There is a second reading of the coloured grid, and it turns the sieve from an algorithm into an identity.

Count the struck cells one way: run the sieve, and count what it strikes. Count them the other way: for each composite, name its smallest prime factor, and add up how many composites name each prime. Both counts are of the same cells, so they must agree — and the second count is precisely the statement that the composites below $n$ are partitioned by their smallest prime factor.

Stated like that it is nearly trivial. Its descendants are not. The same partition, made carefully and with the counting arranged so that errors cancel rather than accumulate, is the beginning of every modern sieve method. Viggo Brun’s sieve, which in 1919 produced the first real theorem about twin primes — that the sum of their reciprocals converges, so they are much rarer than the primes themselves — is this idea with an inclusion–exclusion argument bolted on and its error terms controlled by hand.

Counting one collection in two ways is the whole method. It is the same move that turns a stack of odd numbers into a square, that makes a partition and its conjugate the same set of dots read twice, and that reduces quadratic reciprocity to a rectangle. It is the single most productive idea in elementary number theory, and the sieve is where it first shows up.

Where it stops being enough #

Sieving decides primality for every number in a range at once, and it is the wrong instrument for one number at a time. Trial division — the honest check, dividing by everything up to $\sqrt{n}$ — costs about $\sqrt{n}$ operations, so for a number of two hundred digits it needs a hundred digits’ worth of work and is therefore not merely slow but impossible.

What replaced it is a test that never factors anything at all. Fermat’s little theorem says that for a prime $p$ and any $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod p$. Computing $a^{p-1}$ modulo $p$ takes a few hundred multiplications by repeated squaring, whatever the size of $p$, and if the answer is not $1$ then $p$ is definitely composite — while nothing whatever has been learned about its factors.

That gap, between knowing a number is composite and knowing what it is made of, is not a temporary state of ignorance. It is the foundation modern public-key cryptography is built on, and it exists because the two questions, which sound like one question, are answered by completely different machinery. The sieve answers both at once for small numbers, and neither for large ones.

Where the ladder goes next #

The sieve produces primes by removing everything else, which raises the question the next rung has to answer: does it ever stop producing them? The grids above are finite, and for all they show, the twenty-five primes below a hundred could be most of the primes there are. There is no last prime settles that, with an argument older than any surviving description of the sieve and quite independent of it.

Two other directions lead away from here. The colouring in the second figure asserts that every composite has a smallest prime factor and exactly one — which sounds like nothing and is the fundamental theorem of arithmetic, a statement that fails outright in arithmetics only slightly stranger than this one. And the primes, once produced, can be sorted by properties that have nothing to do with the sieve: some are sums of two squares and some are not, and which is which is decided entirely by a remainder on division by four.

The observation this essay ends where it began. Nothing above ever produced a prime. Every step removed something, and the primes are what nobody had a reason to remove.