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

*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

*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^{1} |
4 | 0 | 2 | 2.500 |

10^{2} |
25 | 3 | 5 | 4.000 |

10^{3} |
168 | 23 | 10 | 5.952 |

10^{4} |
1,229 | 143 | 17 | 8.137 |

10^{5} |
9,592 | 906 | 38 | 10.430 |

10^{6} |
78,498 | 6,116 | 130 | 12.740 |

10^{7} |
664,579 | 44,159 | 339 | 15.050 |

10^{8} |
5,761,455 | 332,774 | 754 | 17.360 |

10^{9} |
50,847,534 | 2,592,592 | 1,701 | 19.670 |

10^{10} |
455,052,511 | 20,758,029 | 3,104 | 21.980 |

10^{11} |
4,118,054,813 | 169,923,159 | 11,588 | 24.280 |

10^{12} |
37,607,912,018 | 1,416,705,193 | 38,263 | 26.590 |

10^{13} |
346,065,536,839 | 11,992,858,452 | 108,971 | 28.900 |

10^{14} |
3,204,941,750,802 | 102,838,308,636 | 314,890 | 31.200 |

10^{15} |
29,844,570,422,669 | 891,604,962,452 | 1,052,619 | 33.510 |

10^{16} |
279,238,341,033,925 | 7,804,289,844,392 | 3,214,632 | 35.810 |

4 ·10^{16} |
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 *n*th prime number *p*(*n*):

*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.

Because of the connection between the Riemann zeta function and π(*x*), the Riemann hypothesis has considerable importance in number theory: if established, it would yield a far better estimate of the error involved in the prime number theorem than is available today.

Helge von Koch in 1901 showed that more specifically, if the Riemann hypothesis is true, the error term in the above relation can be improved to