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