Jelölje π(n) az n-ig terjedő prímszámok számát. A prímszámtétel szerint π(n) úgy nő, mint n/ln(n). Ahogy n egyre nagyobb, n környékén körülbelül minden ln(n)-edik szám prímszám. Egymillió közelében nagyjából minden 14. szám prím. Egymilliárd környékén minden 21.
π(n) az n-ig terjedő prímszámokat számolja (kék lépcső). A prímszámtétel szerint π(n) ~ n/ln(n), vagyis a hányados → 1, ha n → ∞. A logaritmikus integrál, Li(n), még közelebbi közelítés.
Gauss 1800 körül sejtette meg az eredményt prímtáblák tanulmányozása után. 1896-ban egymástól függetlenül Jacques Hadamard és Charles-Jean de la Vallée Poussin bizonyította be, mindketten a Riemann-zéta-függvényt és a komplex analízist használva. Tisztán elemi bizonyítást (komplex analízis nélkül) Selberg és Erdős talált egymástól függetlenül 1948-ban.
Táblázat a prímszámok sűrűségéről különböző nagyságrendeken
| n-ig | Prímek π(n) | Sűrűség ≈ 1/ln(n) |
|---|---|---|
| 1 000 | 168 | 7-ből 1 |
| 1 000 000 | 78 498 | 14-ből 1 |
| 10⁹ | 50 847 534 | 21-ből 1 |
| 10¹² | 37 607 912 018 | 28-ból 1 |
A Riemann-sejtés adná a legélesebb hibabecslést: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Enélkül csak annyit tudunk, hogy a hiba o(n/ln(n)). Ezért a Riemann-sejtés a matematika legfontosabb nyitott problémája: pontosan megmondaná, mennyire kiszámíthatók a prímosztások közötti hézagok.
A pi(n)-re az n/ln(n)-nél pontosabb közelítés a logaritmikus integrál: Li(n) = 2-től n-ig vett ∫ dt/ln(t). Gauss ezt a formát részesítette előnyben. n = 1 000 000 esetén az n/ln(n) 72 382-t ad, míg Li(n) 78 628-at, szemben a pontos 78 498-cal. Li(n) hibája sokkal kisebb. A Riemann-sejtés ezt a hibát pontosan a sqrt(n) * ln(n) nagyságrendjében korlátozná.