# Prime Number Theorem

The Prime Number Theorem (PNT) describes the distribution of prime numbers. Euclid could prove that there is an infinite number of primes, but their location can only be predicted by statistical means, as an approximation. As ordinary numbers get larger and larger, we find fewer and fewer prime numbers scattered among them. This can easily be demonstrated with the “Sieve of Eratosthenes.” It has resulted in a hunt to find a formula for the location of primes, which is also essential for encrypting messages send across public information highways. Evewn though we cannot predict primes (yet?), we find that the distribution of prime numbers is asymptotic, and follows very precise laws. In simple terms, the Prime Number Theorem says that, as **x** approaches infinity, the quotient between x and ln(x) becomes a better and better estimate of the number of primes at or below **x**. That’s not a lot, but it’s as far as we got, and there is still a lot more we can find out about primes.

**Here is some more math:**

For any positive real number *x*, we define

The prime number theorem then states that

where ln(*x*) is the natural logarithm of *x*. This notation means that the limit of the *quotient* of the two functions π(*x*) and *x*/ln(*x*) as *x* approaches infinity is 1; it does **not** mean that the limit of the *difference* of the two functions as *x* approaches infinity is zero.

An even better approximation, and an estimate of the error term, is given by the formula

for *x* → ∞ (see big O notation). Here Li(*x*) is the offset logarithmic integral function.

Here is a table that shows how the three functions (π(*x*), *x*/ln(*x*) and Li(*x*)) compare:

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

10^{1} |
4 | 0 | 2 | 2.500 |

10^{2} |
25 | 3 | 5 | 4.000 |

10^{3} |
168 | 23 | 10 | 5.952 |

10^{4} |
1,229 | 143 | 17 | 8.137 |

10^{5} |
9,592 | 906 | 38 | 10.430 |

10^{6} |
78,498 | 6,116 | 130 | 12.740 |

10^{7} |
664,579 | 44,159 | 339 | 15.050 |

10^{8} |
5,761,455 | 332,774 | 754 | 17.360 |

10^{9} |
50,847,534 | 2,592,592 | 1,701 | 19.670 |

10^{10} |
455,052,511 | 20,758,029 | 3,104 | 21.980 |

10^{11} |
4,118,054,813 | 169,923,159 | 11,588 | 24.280 |

10^{12} |
37,607,912,018 | 1,416,705,193 | 38,263 | 26.590 |

10^{13} |
346,065,536,839 | 11,992,858,452 | 108,971 | 28.900 |

10^{14} |
3,204,941,750,802 | 102,838,308,636 | 314,890 | 31.200 |

10^{15} |
29,844,570,422,669 | 891,604,962,452 | 1,052,619 | 33.510 |

10^{16} |
279,238,341,033,925 | 7,804,289,844,392 | 3,214,632 | 35.810 |

4 ·10^{16} |
1,075,292,778,753,150 | 28,929,900,579,949 | 5,538,861 | 37.200 |

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

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

The theorem was conjectured by Adrien-Marie Legendre in 1798 and proved independently 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. The first of these was provided partly independently by Paul Erdös and Atle Selberg in 1949 although it was previously believed that such proofs with only real variables could **not** be found.