Helpful context:

A random number near $10^9$ is prime with probability roughly 1 in 20. Near $10^{18}$, roughly 1 in 41. Near $2^{2048}$, roughly 1 in 1419. These are not estimates - they follow from a precise theorem, and the theorem has a precise error term that depends on one of the most famous unsolved problems in mathematics.

The question is simple to state: how many primes are there up to $x$? Gauss, working by hand as a teenager around 1791, computed tables of primes and noticed that they thin out at a predictable rate. He conjectured that the density of primes near $x$ is approximately $1 / \ln x$, so the total count up to $x$ is roughly $x / \ln x$. This observation - purely empirical - turned out to be exactly right in the limit. But making it rigorous required a century of work, and the final proof by Hadamard and de la Vallee Poussin in 1896 required the most powerful tools of 19th-century analysis.

What makes the Prime Number Theorem deep is the mechanism behind it. Primes seem irregular and unpredictable locally, yet their global distribution is smooth and governed by an analytic function - the Riemann zeta function - via a connection that runs through the complex plane. The zeros of $\zeta(s)$ control the error in the prime count, and the unresolved question of where those zeros lie - the Riemann Hypothesis - would give the sharpest possible bound on that error.

The Prime Counting Function

The prime counting function $\pi(x)$ counts the number of primes $p \leq x$. Some values:

$x$ $\pi(x)$ $x / \ln x$ $\text{Li}(x)$
$10$ $4$ $4.34$ $5.12$
$100$ $25$ $21.7$ $29.1$
$1000$ $168$ $144.8$ $177.6$
$10^6$ $78{,}498$ $72{,}382$ $78{,}628$
$10^9$ $50{,}847{,}534$ $48{,}254{,}942$ $50{,}849{,}235$

Two approximations appear: $x / \ln x$ (Gauss’s original conjecture) and $\text{Li}(x) = \int_2^x \frac{dt}{\ln t}$ (the logarithmic integral, a refinement). Both are good, but $\text{Li}(x)$ is dramatically better - it tracks $\pi(x)$ to within a few hundred even at $x = 10^9$.

The logarithmic integral arises naturally: if the density of primes near $t$ is $1/\ln t$, then $\pi(x) \approx \int_2^x \frac{1}{\ln t} dt = \text{Li}(x)$.

The Prime Number Theorem

Theorem (Hadamard, de la Vallee Poussin, 1896). As $x \to \infty$,

$$\pi(x) \sim \frac{x}{\ln x},$$

where $f(x) \sim g(x)$ means $\lim_{x \to \infty} f(x)/g(x) = 1$.

Equivalently, the $n$-th prime $p_n$ satisfies $p_n \sim n \ln n$.

The theorem says the ratio $\pi(x) \ln x / x$ converges to 1 - not that the difference converges to zero. The absolute error $|\pi(x) - x/\ln x|$ grows without bound, but it grows more slowly than $x/\ln x$.

The better statement uses $\text{Li}(x)$:

$$\pi(x) = \text{Li}(x) + O\left(x e^{-c\sqrt{\ln x}}\right)$$

for an explicit constant $c > 0$. The error term is smaller than any power of $x$, but larger than $x^{1/2+\varepsilon}$ for any $\varepsilon > 0$ (as far as current methods show without the Riemann Hypothesis).

The Riemann Zeta Function

The key player is the Riemann zeta function, defined for $\text{Re}(s) > 1$ by

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}.$$

Euler had already discovered the Euler product formula:

$$\zeta(s) = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}},$$

where the product runs over all primes. This identity - an equality between a sum over integers and a product over primes - encodes the fundamental theorem of arithmetic analytically. It says: the integers $n^{-s}$ can be “factored” into prime contributions $(1 - p^{-s})^{-1}$, because every integer has a unique prime factorization.

Riemann, in his 1859 paper, extended $\zeta(s)$ to a meromorphic function on all of $\mathbb{C}$, with a single pole at $s = 1$. He showed that $\zeta(s)$ satisfies a functional equation relating its values at $s$ and $1 - s$:

$$\pi^{-s/2} \Gamma(s/2) \zeta(s) = \pi^{-(1-s)/2} \Gamma((1-s)/2) \zeta(1-s).$$

This symmetry reflects the deep connection between $\zeta$ and the distribution of primes.

Values at positive even integers:

$$\zeta(2) = \frac{\pi^2}{6}, \quad \zeta(4) = \frac{\pi^4}{90}, \quad \zeta(6) = \frac{\pi^6}{945}, \quad \zeta(2k) = (-1)^{k+1} \frac{(2\pi)^{2k} B_{2k}}{2(2k)!}$$

where $B_{2k}$ are the Bernoulli numbers. Values at positive odd integers are mysterious: $\zeta(3) \approx 1.202$ (Apery’s constant) was proved irrational by Apery in 1978, but no closed form in terms of known constants is known. Whether $\zeta(5), \zeta(7), \ldots$ are irrational is open.

Zeros and the Explicit Formula

The non-trivial zeros of $\zeta(s)$ are the zeros in the critical strip $0 < \text{Re}(s) < 1$. These are not the “trivial” zeros at $s = -2, -4, -6, \ldots$, which arise from poles of $\Gamma$.

Riemann derived the explicit formula connecting $\pi(x)$ to the zeros. Writing $\rho$ for a non-trivial zero:

$$\pi(x) = \text{Li}(x) - \sum_{\rho} \text{Li}(x^\rho) - \ln 2 + \int_x^{\infty} \frac{dt}{t(t^2-1)\ln t}.$$

Each zero $\rho = \sigma + it$ contributes an oscillatory term $\text{Li}(x^\rho) \approx x^\sigma / (\sigma \ln x)$ times a complex exponential. The real part $\sigma$ controls the magnitude of the oscillation; the imaginary part $t$ controls its frequency.

If all non-trivial zeros have $\text{Re}(\rho) = 1/2$, then every term has magnitude $O(x^{1/2}/\ln x)$, and the total error in $\pi(x)$ is $O(\sqrt{x} \ln x)$. This is the content of the Riemann Hypothesis.

If any zero had $\text{Re}(\rho) > 1/2$, it would cause $\pi(x)$ to oscillate with a larger amplitude, meaning primes are less regularly distributed than the Riemann Hypothesis predicts.

The Riemann Hypothesis

Conjecture (Riemann, 1859). All non-trivial zeros of $\zeta(s)$ lie on the critical line $\text{Re}(s) = 1/2$.

The first few non-trivial zeros (by imaginary part) are approximately $1/2 + 14.13i$, $1/2 + 21.02i$, $1/2 + 25.01i$, $\ldots$ They have been verified numerically for the first $10^{13}$ zeros - all lie on the critical line.

The Riemann Hypothesis is one of the Millennium Prize Problems, with a $1 million prize for a proof or disproof.

Consequence for the error term. If RH holds:

$$|\pi(x) - \text{Li}(x)| \leq \frac{1}{8\pi}\sqrt{x}\ln x \quad \text{for all } x \geq 2657.$$

Without RH, the best unconditional error bound is $O(x e^{-c\sqrt{\ln x}})$, which is smaller than $x^{1-\varepsilon}$ for any $\varepsilon > 0$ but not as small as $O(\sqrt{x} \ln x)$.

Why it matters for primes. The Riemann Hypothesis says primes are distributed as regularly as possible - no large unexpected clumps or gaps. Each zero of $\zeta$ is like a “frequency” in the distribution of primes. Having them all on the line $\text{Re}(s) = 1/2$ means the oscillations are all the same strength, none dominating the others.

Proof Sketch of the PNT

The standard proof connects $\pi(x)$ to $\zeta(s)$ via the Mellin transform of a modified counting function. The key steps:

  1. Define the Chebyshev function $\psi(x) = \sum_{p^k \leq x} \ln p$ (sum of $\ln p$ over prime powers $\leq x$). The PNT is equivalent to $\psi(x) \sim x$.

  2. Show $-\zeta'(s)/\zeta(s) = \sum_{n=1}^\infty \Lambda(n) n^{-s}$ where $\Lambda(n) = \ln p$ if $n = p^k$ and $0$ otherwise (the von Mangoldt function). So $\psi(x) = \sum_{n \leq x} \Lambda(n)$.

  3. Invert via the Perron formula: $\psi(x) = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{-\zeta'(s)}{\zeta(s)} \frac{x^s}{s} ds$ for $c > 1$.

  4. Shift the contour of integration to the left. The residue at $s = 1$ (the pole of $\zeta$) gives the main term $x$. Residues at zeros $\rho$ give the correction terms $-x^\rho/\rho$. The remaining contour integral is a small error term.

  5. The key analytic input: $\zeta(1 + it) \neq 0$ for all real $t \neq 0$. This prevents zeros from approaching the line $\text{Re}(s) = 1$ and is what Hadamard and de la Vallee Poussin proved.

The argument that $\zeta(1 + it) \neq 0$ uses the inequality $3 + 4\cos\theta + \cos 2\theta \geq 0$ (which holds because it equals $2(1 + \cos\theta)^2 \geq 0$) applied to the logarithm of $\zeta$. If $\zeta$ had a zero at $1 + it$, this inequality would be violated.

Practical Implications for Cryptography

The PNT tells cryptographers how many primes to expect when generating large primes for RSA or Diffie-Hellman.

The probability that a random $k$-bit number (near $x = 2^k$) is prime is approximately:

$$\Pr[\text{random } k\text{-bit number is prime}] \approx \frac{1}{\ln 2^k} = \frac{1}{k \ln 2}.$$

To generate a random $k$-bit prime, trial-test uniformly random $k$-bit odd numbers. The expected number of trials is approximately $k \ln 2 / 2$ (dividing by 2 because we test only odd numbers).

Key size $k$ Expected trials
512 bits $\approx 178$
1024 bits $\approx 355$
2048 bits $\approx 710$
4096 bits $\approx 1420$

Each trial runs Miller-Rabin primality testing in $O(k^3)$ time, so finding a $k$-bit prime costs $O(k^4)$ operations - entirely practical even at $k = 4096$.

The PNT also tells you that the supply of primes is essentially unlimited for cryptographic purposes. There are approximately $2^{1024} / (1024 \ln 2) \approx 1.4 \times 10^{305}$ primes with at most 1024 bits - far more than could ever be enumerated or blacklisted.

Summary

Concept Statement Significance
Prime counting function $\pi(x)$: number of primes $\leq x$ $\pi(10^6) = 78{,}498$
PNT $\pi(x) \sim x/\ln x$ Density of primes near $x$ is $1/\ln x$
Logarithmic integral $\pi(x) \approx \text{Li}(x) = \int_2^x dt/\ln t$ Much sharper than $x/\ln x$
Euler product $\zeta(s) = \prod_p (1-p^{-s})^{-1}$ FTA encoded analytically
Explicit formula $\pi(x) = \text{Li}(x) - \sum_\rho \text{Li}(x^\rho) + \cdots$ Zeros control error term
Riemann Hypothesis All non-trivial zeros have $\text{Re}(\rho) = 1/2$ Implies $
Cryptographic application $\sim k \ln 2 / 2$ trials to find $k$-bit prime Makes RSA key generation feasible

Read next: