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.
Watch it run
The same sieve on 1 to 400, computed live in your browser. Each square goes grey the moment it is struck.
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