Numbers that will not split
Twelve sweets can be shared fairly between 2, 3, 4 or 6 children. Thirteen cannot: whichever way you deal them out, someone is left over, unless you give them all to one child or one each to thirteen. A whole number greater than 1 that can only be split those two dull ways is a prime. Its only divisors are 1 and itself. A number with other divisors, like 12, is composite.
The primes start 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Only one of them is even, since every other even number can be split in two. And 1 is left out on purpose, for a reason that comes up below.
Primes matter because they are what every other whole number is made of. Keep splitting a number into factors and you always end at primes: 360 = 2 × 2 × 2 × 3 × 3 × 5. However you go about it, you reach the same primes, the same number of times each. This is called the fundamental theorem of arithmetic, and it is why 1 is not counted as a prime: if it were, you could tack on as many 1s as you liked and the factorisation would no longer be unique.
A spiral of numbers
In 1963 the mathematician Stanisław Ulam, sitting through a long talk, began writing the counting numbers on squared paper. He put 1 in the middle, 2 beside it, and wound the rest round in a square spiral. Then he circled the primes. They did not scatter like salt. Many of them lined up along diagonals.
The scene builds the same spiral. Each tile is one number, and the primes stand up in gold.
Try it: slide Count up to down to 100, a 10 × 10 square, and find 2, 3, 5 and 7 near the middle. Then slide it up to 2,500 and on to 10,000: the numbers get too small to read, and the diagonal lines come out.
Part of the pattern is simple. Next to any number in the spiral sits the number one more or one less, so even and odd numbers alternate like the squares of a chessboard, and every diagonal is all odd or all even. All the primes but 2 are odd, so they can only land on half the diagonals. And the numbers along one diagonal follow a formula: the line running up and to the right from 1 holds 1, 3, 13, 31, 57, which are the values of 4n² − 2n + 1. Some formulas like this hit primes far more often than others. Mathematicians have a well-tested guess for how often each one should, but nobody has proved it.
The sieve of Eratosthenes
How do you find all the primes up to some number? Around 2,200 years ago, Eratosthenes, a Greek scholar in Alexandria, used a method that still bears his name. Write down every number. Circle 2, the first prime, and cross out every multiple of 2. The next number not crossed out, 3, must be prime, since nothing smaller divides it. Circle it and cross out its multiples. Then 5, then 7, and on.
Try it: slide Sieve the spiral slowly from Spiral. Each colour is one prime crossing out its multiples, and the slate counts how many it removed.
Two shortcuts make it fast. When you reach a prime p, you can start crossing at p × p, because every smaller multiple, like p × 2 or p × 3, has a smaller factor and is already crossed. That is why 3 begins at 9 and 5 at 25 in the scene. And you can stop once p × p is bigger than the count: a composite number up to the count must have a factor no bigger than its square root, so it has been crossed already. To find the primes up to 400 you only sieve with the primes up to 20. Whatever has not been crossed out at the end is prime, and in the scene those are exactly the gold tiles.
Why the primes never run out
About 2,300 years ago, Euclid showed that there is no largest prime. Suppose you had a list of every prime there is. Multiply them all together and add 1. The new number leaves a remainder of 1 when divided by any prime on your list, so none of them divides it. But it is either prime itself or made of primes, so some prime is missing from the list. No finite list can be complete.
The largest primes known today have tens of millions of digits, and are found by computers testing numbers of a special form for months at a time.
Gaps that grow, twins that keep coming
The primes thin out as you count. A quarter of the numbers up to 100 are prime, but only one in eight of those up to 10,000. Near a large number N, about one number in every ln N is prime, where ln is the natural logarithm. This is the prime number theorem, proved in 1896, and it means the average gap between neighbouring primes grows slowly, like ln N.
Try it: slide Sieve the spiral all the way to Sieve and gaps, then drag Count up to to its end. Each bar is the gap from one prime to the next. The dashed curve is ln p, and the largest gap shows in amber, on the slate and on the tiles.
Gaps can be as long as you like. The numbers 101! + 2, 101! + 3, and so on up to 101! + 101, where 101! means 1 × 2 × 3 × … × 101, are a hundred composite numbers in a row: the first divides by 2, the next by 3, and so on. Yet the short gaps never seem to stop either. Pairs of primes only 2 apart, like 11 and 13 or 9,857 and 9,859, are called twin primes, and they keep turning up as far as anyone has looked. Whether they go on forever is one of the oldest open questions in mathematics. In 2013 Yitang Zhang proved that some gap below 70 million occurs infinitely often, and other mathematicians have since brought that bound down to 246.
Where primes are used
Multiplying two primes is easy, but given only the result, finding the two primes again is very hard when they each have hundreds of digits. Some of the encryption that protects online payments and messages relies on that one-way street: a public number made by multiplying two secret primes can lock a message that only the holder of the primes can unlock.
What this model leaves out
The spiral is a picture, not a property of the primes. Wind the same numbers in rows, or start the spiral at 41 instead of 1, and different lines appear. Ulam’s diagonals are real, but some of what the eye picks out is chance.
The scene sieves with each prime in turn and crosses each composite number once, in the colour of its smallest prime factor. On paper you would cross 12 twice, once for 2 and once for 3; the result is the same. The count stops at 10,000, where there are 1,229 primes. The gap chart only shows gaps between primes that both fall inside the count, so the gap after the last prime is missing, and the ln p curve describes the average, not any single gap.