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 &pi(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.