Engineering / Mathematics — The Distribution of Primes
The Prime Number Theorem
The prime number theorem, its equivalent formulations, and the logarithmic integral as the superior approximation.
Executive summary
The prime number theorem states that the number of primes below x is asymptotically x over log x. Proved independently by Hadamard and de la Vallee Poussin in 1896, it was the culmination of a century of work.
The logarithmic integral gives a substantially better approximation than x over log x, and understanding why is the entry point to the error term and the Riemann hypothesis.
Learning objectives
- State the theorem and its equivalent forms.
- Compare the two standard approximations.
- Sketch the connection to the Riemann zeta function.
01The theorem
Prime number theorem
π(x) ~ x / ln x, meaning π(x) · ln x / x → 1 as x → ∞.
Equivalently θ(x) ~ x and ψ(x) ~ x.
An immediate consequence is the heuristic that governs prime generation: a random integer near x is prime with probability about 1/ln x. Restricting to odd numbers doubles this, and sieving by small primes improves it further.
Probability a random k-bit odd integer is prime ≈ 2/(k ln 2)02The logarithmic integral
The approximation x/ln x is asymptotically correct but converges slowly and consistently underestimates. The logarithmic integral does much better.
Logarithmic integral
li(x) = ∫₂^x dt / ln t, taken as a principal value.
| x | π(x) | x/ln x | li(x) |
|---|---|---|---|
| 10⁶ | 78,498 | 72,382 | 78,628 |
| 10⁹ | 50,847,534 | 48,254,942 | 50,849,235 |
| 10¹² | 37,607,912,018 | 36,191,206,825 | 37,607,950,281 |
The reason li is better is that the density of primes near t is about 1/ln t, and integrating that density is the natural estimate. Using 1/ln x for the whole range up to x understates the contribution of smaller integers, where primes are denser.
03The analytic connection
The proof runs through the Riemann zeta function ζ(s) = Σ n^{−s}, which encodes the primes through the Euler product.
ζ(s) = ∏_p (1 − p^{−s})^{−1} for Re(s) > 1The Euler product is the analytic statement of unique factorisation. Taking logarithmic derivatives converts it into a sum over prime powers, which is exactly ψ(x), and contour integration transfers information about the zeros of ζ into information about ψ.
The crux of the 1896 proofs was showing ζ(s) has no zeros on the line Re(s) = 1. That single fact is equivalent to the prime number theorem, and how far the zero-free region extends leftward determines the size of the error term.
04Frequently asked questions
Is there an elementary proof?
Yes. Erdos and Selberg gave elementary proofs around 1949, in the technical sense of avoiding complex analysis. They are not simpler — they are considerably more intricate — but they showed the theorem does not require analytic machinery in principle.
Does li(x) always overestimate π(x)?
No, though it does for every x ever computed. Littlewood proved the difference changes sign infinitely often, and the first crossing is known to occur somewhere below about 10^316. This is a standard caution against inferring theorems from numerical evidence.
How is the theorem used in practice?
Almost entirely through the density heuristic. It fixes the expected number of candidates tested during prime generation, which determines key generation time and lets implementations set sensible retry limits.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 86-88.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.