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 *quotient* of the two functions π(*x*) and *x*/ln(*x*) tends to 1 as *x* approaches infinity; it does **not** mean that the *difference* of the two functions tends to zero as *x* approaches infinity.

*n*-th prime number *p*(*n*):

- π(
*x*) = the number of primes that are ≤*x*

- π(
*x*) ~*x*/ ln(*x*)

Here is a table that shows how the two functions compare:

x |
π(x) |
x/ln(x) |
---|---|---|

1,000 | 168 | 145 |

10,000 | 1,229 | 1,086 |

100,000 | 9,592 | 8,686 |

1,000,000 | 78,498 | 72,382 |

10,000,000 | 664,579 | 620,420 |

100,000,000 | 5,761,455 | 5,428,681 |

An even better approximation is given by Gauss' formula

x π(As a consequence of the prime number theorem, one get an asymptotic expression for thex) ~ ∫ 1/ln(x) dx2

*p*(*n*) ~*n*ln(*n*)

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

The theorem was conjectured by [Adrien-Marie Legendre]? in 1798 and first proved 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.

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.