prime number theorem
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. <caldwell@utm.edu>

The ancient Greeks proved (about 300 BC) that there were infinitely many primes. About a century ago, it was shown that

the number of primes not exceeding x (called pi(x)") is asymptotic to x/log x.
This result is called the prime number theorem. We can state this in a more precise form using Riemann's Li function,
pi(x) = Li(x) + O(x*e^(-a*sqrt(log x)))
for some constant a.

The prime number theorem implies that the probability that a random number n is prime, is about 1/log n (technically, the probability a number m chosen from the set {1,2,...,n} is prime is asymptotic to 1/log n). It also imples that the average gap between primes near n is about log n and that log (n#) is about n (n# is the primorial function).

See the document "How Many?" (linked below) for much more information on the prime number theorem and its history.

It is surprisingly difficult to give a reasonable heuristic argument for the prime number theorem (and not coincidentally, the proof of this theorem is rather involved). Greg Martin suggested the following approach. Suppose there is a function f(x) which is the "probability" that the integer x is prime. The integer x is prime with probability f(x), and then divides the larger integers with probability 1/x; so as x changes from x to x+1, f(x) changes to (roughly)

f(x).(1-f(x)/x).
So we have
f '(x) = - f2(x)/x.
The general solution of this differential equation is 1/(log(x) + c). This is a version of the prime number theorem (and the best choice of c is negative one).

See Also: PrimeGaps

Related pages (outside of this work)




Chris K. Caldwell © 1999-2014 (all rights reserved)