Number Theory: An Introduction to Mathematics

364 IX The Number of Prime Numbers

and

S= 1 +

∑∞

n= 1

1 /(n+ 1 )^2 < 1 +

∑∞

n= 1

∫n+ 1

n

dt/t^2 = 1 +

∫∞

1

dt/t^2 = 2.

(In factS=π^2 /6, as Euler (1735) also showed.) Since 1− 1 /p^2 =( 1 − 1 /p)( 1 + 1 /p),
and since 1+x≤ex, it follows that
∏

p≤x

( 1 − 1 /p)−^1 ≤S

∏

p≤x

( 1 + 1 /p)<Se

∑

p≤x^1 /p.

Combining this with the inequality of the previous paragraph, we obtain
∑

p≤x

1 /p>log logx−logS. 

Since the series

∑∞

n= 11 /n

(^2) is convergent, Proposition 1 says that ‘there are more
primes than squares’. Proposition 1 can be made more precise. It was shown by
Mertens (1874) that
∑
p≤x
1 /p=log logx+c+O( 1 /logx),
wherecis a constant(c= 0. 261497 ...).
Letπ(x)denote the number of primes≤x:
π(x)=

∑

p≤x

1.

It may be asked whetherπ(x)has some simple asymptotic behaviour asx→∞.It
is not obvious that this is a sensible question. The behaviour ofπ(x)for small values
ofxis quite irregular. Moreover the sequence of positive integers contains arbitrarily
large blocks without primes; for example, none of the integers

n!+ 2 ,n!+ 3 ,...,n!+n

is a prime. Indeed Euler (1751) expressed the view that “there reigns neither order nor
rule” in the sequence of prime numbers.
From an analysis of tables of primes Legendre (1798) was led to conjecture that,
for large values ofx,π(x)is given approximately by the formula

x/(Alogx−B),

whereA,Bare constants and logxagain denotes the natural logarithm ofx(i.e., to
the basee). In 1808 he proposed the specific valuesA=1,B= 1 .08366.
The first significant results on the asymptotic behaviour ofπ(x)were obtained by
Chebyshev (1849). He proved that, for each positive integern,

lim

x→∞

(

π(x)−

∫x

2

dt/logt

)

lognx/x≤ 0

≤ lim

x→∞

(

π(x)−

∫x

2

dt/logt

)

lognx/x,