The prime number theorem describes the distribution of prime numbers. 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:
As a consequence of the prime number theorem, one get an asymptotic expression for the nth prime number p(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 prior believed that such proofs with only real variables can not be found.
Because of the connection between the Riemann zeta function and π(x), the Riemann hypothesis has considerable importance in number theory: if established, it would yield a far better estimate of the error involved in the prime number theorem than is available today.
Helge von Koch in 1901 showed that more specifically, if the Riemann hypothesis is true, the error term in the above relation can be improved to
The constant involved in the O-notation is unknown.
x
π(x)
π(x) - x/ln(x)
Li(x) - π(x)
x/π(x)
101
4
0
2
2.500
102
25
3
5
4.000
103
168
23
10
5.952
104
1,229
143
17
8.137
105
9,592
906
38
10.430
106
78,498
6,116
130
12.740
107
664,579
44,159
339
15.050
108
5,761,455
332,774
754
17.360
109
50,847,534
2,592,592
1,701
19.670
1010
455,052,511
20,758,029
3,104
21.980
1011
4,118,054,813
169,923,159
11,588
24.280
1012
37,607,912,018
1,416,705,193
38,263
26.590
1013
346,065,536,839
11,992,858,452
108,971
28.900
1014
3,204,941,750,802
102,838,308,636
314,890
31.200
1015
29,844,570,422,669
891,604,962,452
1,052,619
33.510
1016
279,238,341,033,925
7,804,289,844,392
3,214,632
35.810
4 ·1016
1,075,292,778,753,150
28,929,900,579,949
5,538,861
37.200
One can also derive the probability that a random number n is prime: 1/ln(n).