Discrete Mathematics: Elementary and Beyond

6.4 On the Set of Primes 95

0

50

100

150

200

250

300

400 800 1200 1600 2000

FIGURE 6.3. The graph ofπ(n) from 1 to 2000.

Theorem 6.4.3 (The Prime Number Theorem)Letπ(n)denote the
number of primes among 1 , 2 ,...,n. Then

π(n)∼

n

lnn

.

(Here lnnmeans the “natural logarithm,” i.e., to logarithm to the base
e=2. 718281 .... Also recall that the notation means that the quotient

π(n)

/ n

lnn

will be arbitrarily close to 1 asngets large.)

The proof of the Prime Number Theorem is very difficult; the fact that
the number of primes up tonis aboutn/lnnwas observed empirically in
the eighteenth century, but it took more than 100 years until Hadamard
and de la Vall ́ee Poussin proved it in 1896.
As an illustration of the use of this theorem, let us find the answer to a
question that we have posed in the introduction: How many primes with
(say) 200 digits are there? We get the answer by subtracting the number of
primes up to 10^199 from the number of primes up to 10^200. By the Prime
Number Theorem, this number is about

10200

200 ln 10

−

10199

199 ln 10

≈ 1. 95 · 10197.