# The Prime Number Theorem

The prime numbers are distributed among the integers in a very irregular way.
There is hardly a pattern (of course, all primes except two are odd, etc.).
The Prime Number Theorem says something about the *average* distribution
of primes.
The Prime Number Theorem states that the number pi(n) of primes at most n
is asymptotic to n/log(n),
where log(n) is the natural logarithm of n (to the base e).
More precisely, the Prime Number Theorem states that the limit of
the relative error pi(n)/(n/log(n)) converges to 1 when n goes to infinity.
The absolute error pi(n) - n/log(n), however, fluctuates unboundedly
for larger values of n.

Here is a little table to illustrate the Prime Number Theorem:

n pi(n) n/log(n)
--------- ----- --------
10 4 4.3
100 25 21.7
316 65 54.9
1,000 168 144.8
10,000 1229 1085.7
100,000 9592 8685.9
1,000,000 78498 72382.4

Thus, a rough estimate of the number of primes less than 316 is 55.
And a rough estimate of the number of 5-digit primes, that is,
of pi(100,000)-pi(10,000), is 7600 (the actual number is 8363).
The Prime Number Theorem is a deep mathematical result.
It was conjectured from experimental data by Gauss (and also Legendre), and
first proved almost one hundred years later by Hadamard and
de la Vallée Poussin in 1896 using the most powerful methods of modern
mathematics.

## Literature

- Richard Courant and Herbert Robbins,
What Is Mathematics? - An Elementary Approach to Ideas and Methods,
Oxford University Press, 1941, 1969.
- Peter Giblin,
Primes and Programming:
An Introduction to Number Theory with Computing,
Cambridge University Press, 1993.