Primes never stop, but they thin out

There is no last prime: the list goes on forever. But the further out you look, the rarer primes get, and they thin out at a rate you can predict.

Two facts that sound like they fight

A prime is a whole number above 1 that only 1 and itself divide: 2, 3, 5, 7, 11. Write π(x) for the number of primes up to x. Among the first hundred numbers, 25 are prime. Among the first thousand, 168. Among the first ten thousand, 1,229.

Those counts keep growing, yet the share keeps falling: a quarter, then 16.8%, then 12.3%. So there are infinitely many primes, and at the same time zero percent of all numbers are prime. Both statements are true.

Why it is worth knowing how fast

"Rare but never gone" could mean almost anything. Knowing the rate turns it into a count you can use. It tells you roughly how many primes sit below a number too big to check one by one, and how long a search for a prime of a given size should take. The rate is also a deep result: Gauss guessed it, and it took until 1896 for Hadamard and de la Vallée Poussin, working independently, to prove it.

Why the list never ends

Euclid's argument takes a few lines. Suppose you had a finite list of every prime. Multiply them all together and add 1. Dividing that number by any prime on your list leaves remainder 1, so none of them divides it. But every whole number above 1 has at least one prime factor. That factor is a prime missing from your list, so no finite list is complete.

Why they thin out

A big number has many more smaller primes that might divide it. Near 100 a number only has to dodge 2, 3, 5 and 7. Near a million it has to dodge every prime up to 1,000 — there are 168 of them. Survivors get scarcer as the gauntlet grows.

The prime number theorem says how much scarcer. It says π(x) and x/ln x grow in step: their ratio tends to 1 as x grows. Here ln is the natural logarithm, the "log" of the source. Put loosely — our paraphrase, not the book's words — near x about one number in ln x is prime. Near a thousand that is about one in 7; near a million, about one in 14. The gaps grow, but only as slowly as a logarithm, which is why the list never runs dry.

One consequence the source sets as an exercise: since π(x) is about x/ln x, the share π(x)/x is about 1/ln x, which goes to zero. That is the precise sense of "zero percent are prime".

A limit, not a good estimate

The theorem is about the ratio in the long run, and x/ln x is a poor guess at the sizes you can check by hand. At 1,000 it gives about 144.8, against the true 168, and at 10,000 about 1,085.7, against 1,229 — both of those our own arithmetic, from the counts above. By our own count, it is still 6.6% low at ten million. The ratio does creep toward 1, but very slowly.

A small shift helps a lot. Subtracting any fixed number from ln x does not change the limit, and the source calls x/(ln x − 1) the best choice. It gives 169.3 at 1,000 and 1,218.0 at 10,000.

Gauss, the man who guessed the pattern, also counted primes the long way. In an 1849 letter he wrote that there are 216,745 primes below 3,000,000 — 71 short of the mark, which the source calls “wrong but close”. The correct count is 216,816. Our own arithmetic puts x/ln x at about 201,152 there and x/(ln x − 1) at about 215,608.

In short

Euclid shows the primes never stop: any finite list misses one. The prime number theorem shows how they thin: up to x there are about x/ln x of them, in the sense that the ratio tends to 1. The share of primes falls toward zero, but slowly enough that there is always another one.