Prime Number Theorem

The Prime Number Theorem is one of the most famous theorems in mathematics. It states that the number of primes not exceeding n is asymptotic to <math>\frac{n}{\log(n)}</math>, where log(n) is the logarithm of (n) to the base e.

The number of primes not exceeding n is commonly written as <math>\pi(n)</math> the Prime counting function, and an asymptotic relationship between a(n) and b(n) is commonly designated as a(n)~b(n). (This does not mean that a(n)-b(n) is small as n increases. It means the ratio of a(n) to b(n) approaches one as n increases.)

The Prime Number Theorem thus states that <math> \pi(n) </math>~<math> n/ \log(n)</math> .

In other words, the limit (as n approaches infinity) of the ratio of pi(n) to n/log(n) is one. Put a third way, n/log(n) is a good approximation for <math>\pi(n)</math>.

Equivalent Statements

Carl Friedrich Gauss conjectured the equivalent statement that <math>\pi(x)</math> was asymptotic to <math>\mbox{Li}(x)</math> defined as:

<math> \mbox{Li}(x) = \int_2^x \frac{dt}{\ln t}</math>.

In fact, for large x this turns out to be a better approximation than <math>\pi(x)</math>. The size of the error <math>\mbox{Li}(x) - \pi(x) </math> is closely related to the behavior of the Riemann Zeta function