Write π(n) for the number of primes up to n. The Prime Number Theorem says π(n) grows like n/ln(n). As n gets larger, about 1 in every ln(n) numbers near n is prime. Near one million, roughly 1 in 14 numbers is prime. Near one billion, 1 in 21.
π(n) counts the primes up to n (blue staircase). The Prime Number Theorem says π(n) ~ n/ln(n) — the ratio → 1 as n → ∞. The logarithmic integral Li(n) is even closer.
Gauss conjectured the result around 1800 after studying prime tables. It was proved independently in 1896 by Jacques Hadamard and Charles-Jean de la Vallée Poussin, both using the Riemann zeta function and complex analysis. A purely elementary proof (without complex analysis) was found independently by Selberg and Erdős in 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 |
The Riemann Hypothesis would give the sharpest bound on the error: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Without it, we only know the error is o(n/ln(n)). This is why the Riemann Hypothesis is mathematics' most important open problem: it would tell us exactly how predictable prime gaps are.
A more accurate approximation to pi(n) than n/ln(n) is the logarithmic integral Li(n) = integral from 2 to n of dt/ln(t). Gauss preferred this form. For n = 1,000,000: n/ln(n) gives 72,382 while Li(n) gives 78,628, versus the exact count of 78,498. The error of Li(n) is far smaller. The Riemann Hypothesis would bound this error precisely at sqrt(n) * ln(n).