Prime number theorem

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

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

The prime number theorem then states that

π(x) ~ x / ln(x)

where ln(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.

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
    π(x)  ~  ∫ 1/ln(x) dx 
             2

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

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.