Beteckna med π(n) antalet primtal upp till n. Primtalssatsen säger att π(n) växer ungefär som n/ln(n). När n blir större är ungefär 1 av varje ln(n) tal nära n ett primtal. Nära en miljon är ungefär 1 av 14 tal ett primtal. Nära en miljard, 1 av 21.
π(n) raknar primtal upp till n (bla trappsteg). Primtalssatsen sager att π(n) ~ n/ln(n) — kvoten → 1 nar n → ∞.
Gauss antog resultatet runt 1800 efter studier av primtalstabeller. Det bevisades självständigt 1896 av Jacques Hadamard och Charles-Jean de la Vallée Poussin, båda med Riemanns zetafunktion och komplex analys. Ett rent elementärt bevis (utan komplex analys) hittades självständigt av Selberg och Erdős 1948.
Table showing density of primes at various scales
| Up to n | Primes π(n) | Density ≈ 1/ln(n) |
|---|---|---|
| 1 000 | 168 | 1 in 7 |
| 1 000 000 | 78 498 | 1 in 14 |
| 10⁹ | 50 847 534 | 1 in 21 |
| 10¹² | 37 607 912 018 | 1 in 28 |
Riemann-hypotesen skulle ge den skarpaste gränsen för felet: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Utan den vet vi bara att felet är o(n/ln(n)). Det är därför Riemann-hypotesen är matematikens viktigaste öppna problem: den skulle berätta exakt hur förutsägbara primtalsgap är.
En mer exakt approximation av pi(n) än n/ln(n) är den logaritmiska integralen Li(n) = integralen från 2 till n av dt/ln(t). Gauss föredrog denna form. För n = 1 000 000: n/ln(n) ger 72 382 medan Li(n) ger 78 628, jämfört med exakta antalet 78 498. Felet hos Li(n) är mycket mindre. Riemann-hypotesen skulle begränsa detta fel precis vid sqrt(n) * ln(n).