# Prime number theorem

The prime number theorem is the statement that the prime-counting function π(x), the number of primes not exceeding x, satisfies \( \pi(x) \sim x/\ln x \) as \( x \to \infty \), meaning that the ratio of the two sides approaches 1.<sup>[1](https://dlmf.nist.gov/27.2)</sup> Conjectured by Gauss around 1792 and by Legendre in 1798, it was first proved in 1896, independently, by [Jacques Hadamard](https://www.edgepedia.org/jacques-hadamard) and Charles de la Vallée Poussin, working through the [Riemann zeta function](https://www.edgepedia.org/riemann-zeta-function).<sup>[2](https://www.hadamard.fr/actualites/theoreme-nombres-premiers-hadamard-vallee-poussin)</sup><sup> • </sup><sup>[3](https://mathshistory.st-andrews.ac.uk/Biographies/Vallee_Poussin/)</sup>

| Key fact | Detail |
|---|---|
| Statement | \( \pi(x) \sim x/\ln x \); equivalently the nth prime satisfies \( p_n \sim n\ln n \)<sup>[1](https://dlmf.nist.gov/27.2)</sup> |
| Conjecture | Gauss, around 1792, from prime tables; Legendre, 1798, with a correcting constant<sup>[2](https://www.hadamard.fr/actualites/theoreme-nombres-premiers-hadamard-vallee-poussin)</sup> |
| First proof | 1896, independently by Hadamard and de la Vallée Poussin, via the zeta function<sup>[2](https://www.hadamard.fr/actualites/theoreme-nombres-premiers-hadamard-vallee-poussin)</sup> |
| Chebyshev's bounds (1851) | π(x) trapped between 0.92129 and 1.10556 times x/ln x<sup>[2](https://www.hadamard.fr/actualites/theoreme-nombres-premiers-hadamard-vallee-poussin)</sup> |
| Classical error term | \( \pi(x) = \operatorname{Li}(x) + O(x\exp(-c\sqrt{\ln x})) \) from the de la Vallée Poussin zero-free region<sup>[4](https://terrytao.wordpress.com/2021/02/12/246b-notes-4-the-riemann-zeta-function-and-the-prime-number-theorem/)</sup><sup> • </sup><sup>[5](https://www.homepages.ucl.ac.uk/~ucahpet/IANTnotes2018.pdf)</sup> |
| Best known error | \( |\psi(x)-x|/x \ll \exp(-\omega(x))(\log x)^9/(\log\log x)^3 \) with \( \omega(x) \) of order \( (\log x)^{3/5}/(\log\log x)^{1/5} \)<sup>[6](https://arxiv.org/abs/2411.13791)</sup> |
| Elementary proof | Selberg, Ann. of Math. 50 (1949), 305–313; Erdős, Proc. Nat. Acad. Sci. 35 (1949), 374–384<sup>[7](https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/on-the-elementary-proof-of-the-prime-number-theorem/D525D90A57B24473D7753D084AD0D799)</sup> |

## Statement and equivalent forms

The theorem is usually written \( \pi(x) \sim x/\ln x \), where \( \pi(x) = \sum_{p \le x} 1 \). The DLMF records two equivalent formulations: the nth prime in increasing order satisfies \( p_n \sim n\ln n \), and the theorem is equivalent to either \( \lim_{x\to\infty} \theta(x)/x = 1 \) or \( \lim_{x\to\infty} \psi(x)/x = 1 \), where θ and ψ are the Chebyshev prime-counting functions that weight each prime, or prime power, by a logarithm.<sup>[1](https://dlmf.nist.gov/27.2)</sup><sup> • </sup><sup>[11](https://mathworld.wolfram.com/PrimeNumberTheorem.html)</sup>

A second, numerically sharper version replaces \( x/\ln x \) with the logarithmic integral \( \operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t} \). Dirichlet formulated the conjecture in this form in the 1830s; since \( \operatorname{Li}(x) \sim x/\ln x \) by integration by parts, the two statements are equivalent, but the analytic proof in fact delivers \( \pi(x) = \operatorname{Li}(x) + O(x\exp(-c\sqrt{\log x})) \).<sup>[5](https://www.homepages.ucl.ac.uk/~ucahpet/IANTnotes2018.pdf)</sup> At \( x = 1000 \), for example, \( x/\ln x \approx 144.76 \) against the true count of 168, while \( \operatorname{Li}(1000) \approx 176.56 \), so the logarithmic integral is the closer of the two approximations.<sup>[12](https://androma.org/page/Prime%20Counting%20Function)</sup>

## History before the proof

**Gauss and Legendre.** Gauss reported that, as a young man, he tabulated the number of primes in intervals himself and studied a table of primes compiled by Johann Lambert (1728–1777), concluding that behind its fluctuations the density of primes is on average inversely proportional to the logarithm.<sup>[8](https://old.maa.org/node/1732760)</sup> In the second edition of his text, published in 1808, Legendre asserted that π(x) is closely approximated by a quotient involving \( \log x - 1.08366 \), a constant he apparently introduced to fit the data better; neither he nor Gauss explained how the natural logarithm entered their formulas.<sup>[9](https://calteches.library.caltech.edu/3832/)</sup> A simple exercise in calculus demonstrates that Li(x), Gauss's logarithmic integral, is asymptotic to x/log x; hence the two conjectures amount to the same thing as the theorem in its modern form.<sup>[9](https://calteches.library.caltech.edu/3832/)</sup>

**Chebyshev and Riemann.** In 1851 Chebyshev bounded π(x) between 0.92129 and 1.10556 times x/ln x, the first substantial result on the density of the primes but half a century short of the theorem itself.<sup>[2](https://www.hadamard.fr/actualites/theoreme-nombres-premiers-hadamard-vallee-poussin)</sup><sup> • </sup><sup>[13](https://docs.numerisect.com/mathematics/distribution/)</sup> Riemann's 1859 memoir connected the distribution of primes to the zeros of the zeta function, providing the framework the 1896 proofs used.<sup>[14](https://arxiv.org/abs/1003.0098)</sup>

## The 1896 proofs and the zeta function

Hadamard and de la Vallée Poussin proved the theorem independently in 1896, using Riemann's ideas.<sup>[2](https://www.hadamard.fr/actualites/theoreme-nombres-premiers-hadamard-vallee-poussin)</sup><sup> • </sup><sup>[15](https://uclouvain.be/fr/instituts-recherche/irmp/charles-de-la-vallee-poussin)</sup> The complex-analytic proof hinges on the Riemann zeta function \( \zeta(s) \), whose logarithmic derivative satisfies \( \frac{\zeta'(s)}{\zeta(s)} = -\sum_{n=1}^{\infty} \Lambda(n)n^{-s} \), linking the function to primes through the von Mangoldt function Λ.<sup>[4](https://terrytao.wordpress.com/2021/02/12/246b-notes-4-the-riemann-zeta-function-and-the-prime-number-theorem/)</sup><sup> • </sup><sup>[16](https://people.maths.ox.ac.uk/greenbj/papers/primenumbers.pdf)</sup> The decisive step is showing that \( \zeta(s) \) has no zeros on the line \( \operatorname{Re}(s) = 1 \); de la Vallée Poussin later showed this follows from the elementary trigonometric identity \( \cos 2\theta = 2\cos^2\theta - 1 \), an observation that shortened his original proof by 24 pages.<sup>[9](https://calteches.library.caltech.edu/3832/)</sup>

## Zero-free regions and the error term

The size of the error in the theorem is governed by how far the zero-free region around the line \( \operatorname{Re}(s) = 1 \) extends into the critical strip. The classical zero-free region of de la Vallée Poussin, \( \sigma \ge 1 - \frac{c}{\ln(1+|t|)} \) for a sufficiently small absolute constant c, improves the qualitative \( o(x) \) error to \( O(x\exp(-c\sqrt{\ln x})) \), with the corresponding statement for π(x) using the logarithmic integral.<sup>[4](https://terrytao.wordpress.com/2021/02/12/246b-notes-4-the-riemann-zeta-function-and-the-prime-number-theorem/)</sup> The Vinogradov–Korobov region, \( \zeta(\sigma+it) \neq 0 \) for \( \sigma \ge 1 - \nu(t) \) with \( \nu(t) = A_0(\log t)^{-2/3}(\log\log t)^{-1/3} \), yields an error \( \psi(x) - x \ll x\exp(-(1-\varepsilon)\omega(x)) \) where \( \omega(x) \) is of order \( (\log x)^{3/5}(\log\log x)^{-1/5} \); a 2024 analysis by Daniel R. Johnston of the University of New South Wales Canberra, combining such a region with zero-density estimates, gives \( \frac{|\psi(x)-x|}{x} \ll \exp(-\omega(x))\frac{(\log x)^9}{(\log\log x)^3} \), with the lowest known constant in the region being \( c = 53.989 \).<sup>[6](https://arxiv.org/abs/2411.13791)</sup><sup> • </sup><sup>[17](https://arxiv.org/abs/2508.02041)</sup> For small \( |t| \), the sharpest published zero-free region is due to Mossinghoff, Trudgian, and Yang: no zeros for \( \sigma > 1 - \frac{15.558691}{\log|t|} \) when \( |t| \ge 2 \).<sup>[18](https://doi.org/10.1016/j.jmaa.2024.128124)</sup>

The Riemann Hypothesis, which places all nontrivial zeros on the line \( \operatorname{Re}(s) = 1/2 \), is believed, and is in fact equivalent to the statement, that \( \pi(x) = \operatorname{li}(x) + O(\sqrt{x}) \).<sup>[10](https://people.cs.uchicago.edu/~laci/reu03/notes11/node3.html)</sup>

## The elementary proof

In 1948 and 1949 the theorem was proved a second way, without complex analysis. A scriptum written up by J. G. van der Corput from lectures [Paul Erdős](https://www.edgepedia.org/paul-erdos) gave in Amsterdam in 1948 was the first printed account of the elementary proof by [Atle Selberg](https://www.edgepedia.org/atle-selberg) and Erdős; Selberg then published "An elementary proof of the prime number theorem" in [Annals of Mathematics](https://www.edgepedia.org/annals-of-mathematics) 50 (1949), pages 305–313, and Erdős published his method in Proceedings of the National Academy of Sciences 35 (1949), pages 374–384.<sup>[19](https://emis.muni.cz/classics/Erdos/cit/03818106.htm)</sup><sup> • </sup><sup>[7](https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/on-the-elementary-proof-of-the-prime-number-theorem/D525D90A57B24473D7753D084AD0D799)</sup> "Elementary" here means that the methods of higher analysis are not used and, in particular, that the result \( \zeta(1+it) \neq 0 \) for \( t \neq 0 \), which is in a certain sense equivalent to the prime number theorem, is not assumed.<sup>[19](https://emis.muni.cz/classics/Erdos/cit/03818106.htm)</sup> The key ingredient in almost all elementary proofs is Selberg's 1948 prime number lemma; later work has related the error term in that lemma directly to the error term in the theorem itself.<sup>[20](https://libres.uncg.edu/ir/listing.aspx?id=17407)</sup> Wright's 1951 modification of Selberg's proof, which smooths the weighting in the Selberg inequality by iterating it, is described by Norman Levinson of MIT as perhaps the simplest elementary proof; Levinson showed that integrating the Selberg inequality first makes the proof require less ingenuity and removes the need for proof by contradiction.<sup>[7](https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/on-the-elementary-proof-of-the-prime-number-theorem/D525D90A57B24473D7753D084AD0D799)</sup>

## Why the logarithmic integral fits

The fit between π(x) and Li(x) is far better than that between π(x) and x/log x, a fact that Goldston noted had been the subject of intensive but largely unsuccessful investigation for a hundred years. One explanation derives Li(x) as a continuum approximation of a sum over intervals \( s_k = \{p_k^2, \ldots, p_{k+1}^2-1\} \), each fully sieved by the first k primes: the estimate \( x/\log x \) ignores that each sieve step k completes the sieving of its interval, while Li(x) accounts for it.<sup>[21](https://arxiv.org/abs/1311.1093)</sup> Riemann himself estimated the prime-counting function by \( \pi(n) \sim \operatorname{Li}(n) - \tfrac{1}{2}\operatorname{Li}(n^{1/2}) \), a better approximation than Li(n) alone for \( n < 10^7 \), and his fuller Riemann function \( R(x) = \sum_{n=1}^{\infty} \frac{\mu(n)}{n}\operatorname{Li}(x^{1/n}) \) improves on Li(x) by about a factor of 10 for \( n < 10^9 \).<sup>[11](https://mathworld.wolfram.com/PrimeNumberTheorem.html)</sup>

## References

1. [DLMF §27.2, Functions of Number Theory, NIST](https://dlmf.nist.gov/27.2)
2. [Le théorème des nombres premiers : Hadamard et 1896, hadamard.fr](https://www.hadamard.fr/actualites/theoreme-nombres-premiers-hadamard-vallee-poussin)
3. [Charles de la Vallée Poussin (1866–1962), MacTutor History of Mathematics](https://mathshistory.st-andrews.ac.uk/Biographies/Vallee_Poussin/)
4. [Terry Tao, 246B Notes 4: The Riemann zeta function and the prime number theorem (2021)](https://terrytao.wordpress.com/2021/02/12/246b-notes-4-the-riemann-zeta-function-and-the-prime-number-theorem/)
5. [Analytic Number Theory notes, University College London (2018)](https://www.homepages.ucl.ac.uk/~ucahpet/IANTnotes2018.pdf)
6. [Daniel R. Johnston, Zero-density estimates and the optimality of the error term in the prime number theorem, arXiv:2411.13791 (2024)](https://arxiv.org/abs/2411.13791)
7. [N. Levinson, On the Elementary Proof of the Prime Number Theorem, Proc. Edinburgh Math. Soc. 15 (1966), 141–146](https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/on-the-elementary-proof-of-the-prime-number-theorem/D525D90A57B24473D7753D084AD0D799)
8. [Dominic Klyve, The Origin of the Prime Number Theorem, MAA Convergence (2019)](https://old.maa.org/node/1732760)
9. [A Centennial History of the Prime Number Theorem, Caltech Engineering & Science (1996)](https://calteches.library.caltech.edu/3832/)
10. [Primality testing notes, University of Chicago](https://people.cs.uchicago.edu/~laci/reu03/notes11/node3.html)
11. [Prime Number Theorem, Wolfram MathWorld](https://mathworld.wolfram.com/PrimeNumberTheorem.html)
12. [Prime Counting Function, Androma](https://androma.org/page/Prime%20Counting%20Function)
13. [The distribution of primes, Numerisect](https://docs.numerisect.com/mathematics/distribution/)
14. [Analytic implications from the remainder term of the prime number theorem, arXiv:1003.0098](https://arxiv.org/abs/1003.0098)
15. [Charles de la Vallée Poussin, Université catholique de Louvain](https://uclouvain.be/fr/instituts-recherche/irmp/charles-de-la-vallee-poussin)
16. [Ben Green, notes on the zero-free region and the prime number theorem](https://people.maths.ox.ac.uk/greenbj/papers/primenumbers.pdf)
17. [C. Bellotti, A new zero-density estimate for ζ(s) and the error term in the Prime Number Theorem, arXiv:2508.02041 (2025)](https://arxiv.org/abs/2508.02041)
18. [Explicit bounds on ζ(s) in the critical strip and a zero-free region, Journal of Mathematical Analysis and Applications (2024)](https://doi.org/10.1016/j.jmaa.2024.128124)
19. [Zentralblatt entry 038.18106, Publications of Paul Erdős, EMS](https://emis.muni.cz/classics/Erdos/cit/03818106.htm)
20. [On the Prime Number Lemma of Selberg, NC DOCKS](https://libres.uncg.edu/ir/listing.aspx?id=17407)
21. [The origin of the logarithmic integral in the prime number theorem, arXiv:1311.1093](https://arxiv.org/abs/1311.1093)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Analytic number theory › Primes and factorization*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license