** Next:** Fine distribution of primes
** Up:** Multiplicative Number Theory and
** Previous:** Primality testing and factorization

If we continue to enumerate the prime
positive integers, we find that although they occur less and less
frequently there still seems to be an unending supply of them. Later, we
shall prove that there are in fact infinitely many prime numbers. This
theorem first appeared in Euclid's Elements. After establishing that
fact, there still remains the general question of how the primes are
distributed among the integers. There can be long stretches without
primes, and also sudden bunches of primes. This gives their distribution
an appearance of randomness. After much calculation, Gauss (at age
fifteen) conjectured the approximate size of the function
defined to be the number of primes less than or equal to *X*.
First established almost a century later in the 1890's, Gauss'
conjecture can be stated as the following limit:

This says that for very large values of *X* the number
is very
close to .
Here,
is the natural logarithm (i.e. to
the base *e*). This limit is known today as the ``prime number
theorem.''
Actually, Gauss discovered a function much closer to the value of the
prime number counting function .
This is the
**logarithmic integral**

where
means the natural logarithm.
Riemann conjectured that the difference is just a shade above .
This is an equivalent form of **Riemann's Hypothesis**:

for any
.
This is largely agreed to be the most
important unsolved problem in number theory.

** Next:** Fine distribution of primes
** Up:** Multiplicative Number Theory and
** Previous:** Primality testing and factorization
*David J. Wright*

*2000-08-24*