The Prime Number Theorem

In the wake of Euclid’s proof of the infinitude of the primes, the question of how the primes were distributed among the integers became central — a question that has intrigued and challenged mathematicians ever since. The sieve of Eratosthenes provided a simple but very inefficient means of identifying which integers were prime, but attempts to find explicit, closed formulas for the nth prime, or for the number π(x) of primes less than or equal to a given number x, proved fruitless. Eventually extensive tables of integers and their least factors were compiled, detailed examination of which suggested that the apparently unpredictable occurrence of primes in the sequence of integers nonetheless exhibited some statistical regularity. In particular, in 1792 Euler asserted that for large values of x, π(x) was approximately given by $$\dfrac{x} {\ln x}$$ ; six years later, Legendre suggested $$\dfrac{x} {\ln x - 1}$$ and (wrongly) $$\dfrac{x} {\ln x - 1.0836}$$ as better approximations; and in 1849, in a letter to his student Encke (translated in the appendix to Goldstein (1973)), Gauss mentioned his apparently long-held belief that the logarithmic integral $$\displaystyle{ \text{li}(x) =\int _{ 2}^{x}\dfrac{1} {\ln t}\,\mathit{dt} }$$ gave a still better approximation. Using the notation f(x) ∼ g(x) to denote the equivalence relation defined by $$\lim _{x\rightarrow \infty }\dfrac{f(x)} {g(x)} = 1$$ , those conjectures may be expressed in asymptotic form by the statements PNT $$\displaystyle{ \pi (x) \sim \dfrac{x} {\ln x},\quad \pi (x) \sim \dfrac{x} {\ln x - 1},\quad \text{and}\quad \pi (x) \sim \text{li}(x). }$$