Working notes on the primes

Grant Golland’s working notes on how the prime numbers are spread out. Every figure is computed here from a sieve of all 5 761 455 primes below 100 000 000, or with mpmath, and its caption says how. A sibling site, Zeta Zeros, covers the zeros that control these patterns.

Sentences carry a flag: Settled for proved theorems or computations on a stated range, Open for conjectures. A numerical match is never a proof.

Step 1

Primes and the sieve

A prime is a whole number above 1 whose only divisors are 1 and itself. Every whole number above 1 is a product of primes in exactly one way, so primes are the atoms of multiplication.

  • Settled Euclid (Elements IX.20, about 300 BC): there are infinitely many primes. Multiply any finite list together and add 1; the result has a prime factor not on the list.
  • Settled Uniqueness of factorization (the fundamental theorem of arithmetic) is also in Euclid, in substance, and was stated in full by Gauss in 1801.

The sieve of Eratosthenes

To list the primes up to a bound, write out the numbers and strike every multiple of 2 after 2, then every multiple of 3 after 3, and so on. A number that survives has no smaller factor, so it is prime. You can stop at the square root of the bound: a composite number always has a factor no bigger than its square root.

Numbers 1 to 120 in a 12-column grid. Multiples of 2, 3, 5 and 7 are struck in turn (colours); the 30 survivors greater than 1 are the primes up to 120. Only primes up to √120 ≈ 10.95 need to sieve.
Drawn from a direct sieve of 1 to 120: 30 primes survive, matching π(120) = 30 from the large sieve. Colour shows the smallest prime that strikes each number. Motion is off if your system asks for reduced motion.

Watch it run

The same sieve on 1 to 400, computed live in your browser. Each square goes grey the moment it is struck.

Computed in the page by JavaScript; nothing is precomputed. With reduced motion the finished sieve is shown at once. There are 78 primes up to 400.

Every other figure on this site comes from the same idea, scaled up: a sieve of every number below 100 000 000 run on this site’s build machine.

Reading path · step 2 of 11