Označme π(n) počet prvočísel do n. Věta o prvočíslech říká, že π(n) roste jako n/ln(n). Čím větší je n, tím přibližně 1 z každých ln(n) čísel poblíž n je prvočíslo. V okolí jednoho milionu je prvočíslem zhruba 1 ze 14 čísel. V okolí jedné miliardy 1 z 21.
π(n) počítá prvočísla do n (modré schody). Věta o prvočíslech říká, že π(n) ~ n/ln(n) – poměr → 1, když n → ∞. Logaritmický integrál Li(n) je ještě bližší.
Gauss výsledek vyslovil jako domněnku kolem roku 1800 po studiu tabulek prvočísel. Nezávisle jej v roce 1896 dokázali Jacques Hadamard a Charles-Jean de la Vallée Poussin, oba pomocí Riemannovy zeta funkce a komplexní analýzy. Čistě elementární důkaz (bez komplexní analýzy) našli nezávisle Selberg a Erdős v roce 1948.
Tabulka ukazující hustotu prvočísel v různých měřítkách
| Do n | Prvočísla π(n) | Hustota ≈ 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 |
Riemannova hypotéza by dala nejostřejší odhad chyby: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Bez ní víme jen to, že chyba je o(n/ln(n)). Právě proto je Riemannova hypotéza nejdůležitějším otevřeným problémem matematiky: řekla by nám přesně, jak předvídatelné jsou mezery mezi prvočísly.
Přesnější aproximací pi(n) než n/ln(n) je logaritmický integrál Li(n) = integrál od 2 do n z dt/ln(t). Této formě dával přednost Gauss. Pro n = 1 000 000: n/ln(n) dává 72 382, zatímco Li(n) dává 78 628, oproti přesnému počtu 78 498. Chyba Li(n) je mnohem menší. Riemannova hypotéza by tuto chybu přesně omezila hodnotou sqrt(n) * ln(n).