Prime Number Theorem

The prime number theorem (PNT) describes the distribution of prime numbers. For any positive real number x, we define

$\pi(x)={\rm the\ number\ of\ primes\ that\ are\ }\leq x$

The prime number theorem then states that

$\pi(x)\approx\frac{x}{\ln(x)}$

where ln(x) is the natural logarithm of x. This notation means that the limit of the quotient of the two functions π(x) and x/ln(x) as x approaches infinity is 1; it does not mean that the limit of the difference of the two functions as x approaches infinity is zero.

An even better approximation, and an estimate of the error term, is given by the formula

$\pi(x)={\rm Li} (x) + O \left(x e^{-\frac{1}{15}\sqrt{\ln(x)}}\right)$

for x → ∞ (see big O notation). Here Li(x) is the offset logarithmic integral function.

Here is a table that shows how the three functions (π(x), x/ln(x) and Li(x)) compare:

x	π(x)	π(x) - x/ln(x)	Li(x) - π(x)	x/π(x)
10¹	4	0	2	2.500
10²	25	3	5	4.000
10³	168	23	10	5.952
10⁴	1,229	143	17	8.137
10⁵	9,592	906	38	10.430
10⁶	78,498	6,116	130	12.740
10⁷	664,579	44,159	339	15.050
10⁸	5,761,455	332,774	754	17.360
10⁹	50,847,534	2,592,592	1,701	19.670
10¹⁰	455,052,511	20,758,029	3,104	21.980
10¹¹	4,118,054,813	169,923,159	11,588	24.280
10¹²	37,607,912,018	1,416,705,193	38,263	26.590
10¹³	346,065,536,839	11,992,858,452	108,971	28.900
10¹⁴	3,204,941,750,802	102,838,308,636	314,890	31.200
10¹⁵	29,844,570,422,669	891,604,962,452	1,052,619	33.510
10¹⁶	279,238,341,033,925	7,804,289,844,392	3,214,632	35.810
4 ·10¹⁶	1,075,292,778,753,150	28,929,900,579,949	5,538,861	37.200

As a consequence of the prime number theorem, one get an asymptotic expression for the nth prime number p(n):

$p(n)\sim n\ln(n).$

One can also derive the probability that a random number n is prime: 1/ln(n).

The theorem was conjectured by Adrien-Marie Legendre in 1798 and proved independently by Hadamard and de la Vallée Poussin in 1896. The proof used methods from complex analysis, specifically the Riemann zeta function. Nowadays, so-called "elementary" proofs are available that only use number theoretic means. The first of these was provided partly independently by Paul Erdös and Atle Selberg in 1949 although it was previously believed that such proofs with only real variables could not be found