There are infinitely many primes, but how many up to a given point? Write $\pi(x)$ for the number of primes $p \le x$ (this $\pi$ has nothing to do with $3.14159\dots$). So $\pi(10) = 4$ and $\pi(100) = 25$.
The prime number theorem (proved in 1896 by Hadamard and de la Vallée Poussin): $$\pi(x) \sim \frac{x}{\ln x}, \quad\text{meaning}\quad \lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1.$$ Here $\ln$ is the natural logarithm. An equivalent way to say it: near a large number $x$, roughly one number in $\ln x$ is prime.
| $x$ | $\pi(x)$ | $x / \ln x$ | ratio |
|---|---|---|---|
| $10^{3}$ | 168 | 145 | 1.16 |
| $10^{4}$ | 1,229 | 1,086 | 1.13 |
| $10^{6}$ | 78,498 | 72,382 | 1.08 |
| $10^{9}$ | 50,847,534 | 48,254,942 | 1.05 |
Why it works
Worked example: Using the estimate
- $\ln 10^{6} = 6 \ln 10 \approx 6 \cdot 2.302585 = 13.8155$.
- $10^{6} / 13.8155 \approx 72{,}382$.
- The estimate is about $6{,}100$ too low, roughly $8\%$ of the true count. At $10^{9}$ it is $5\%$ low.
Answer: About $72{,}382$, an underestimate.
Worked example: Long gaps between primes
- Take $6! = 720$ and look at $722, 723, 724, 725, 726$, that is, $6! + j$ for $j = 2, \dots, 6$.
- $j$ divides $6!$ and divides $j$, so $j \mid 6! + j$: $722 = 2 \cdot 361$, $723 = 3 \cdot 241$, $724 = 4 \cdot 181$, $725 = 5 \cdot 145$, $726 = 6 \cdot 121$.
- The same trick with $n! + 2, \dots, n! + n$ gives $n - 1$ composites in a row, so gaps between primes can be as long as you like.
Answer: $722$ through $726$.
Worked example: Why cryptographers care
- Near $x = 10^{100}$, about one number in $\ln 10^{100} = 100 \ln 10 \approx 230$ is prime.
- So a random 100-digit odd number is prime with probability about $2/230 = 1/115$: a computer finds one after about a hundred tries. RSA keys are made this way.
Answer: About $1$ in $230$.
Common mistake
Key idea