for some constant B2 . (Note: B2 ≈ 0.832429065662.)

5.4 The sieve of Eratosthenes

As an application of Theorem 5.10, consider the sieve of Eratosthenes.

This is an algorithm for generating all the primes up to a given bound k. It

uses an array A[2 . . . k], and runs as follows.

for n ← 2 to k√ A[n] ← 1

do

for n ← 2 to k do

if A[n] = 1 then

i ← 2n; while i ¤ k do { A[i] ← 0; i ← i + n }

When the algorithm ¬nishes, we have A[n] = 1 if and only if n is prime,

for n = 2, . . . , k. This can easily be proven using the fact (see Exercise 1.1)

that a composite number n between 2 and k must be divisible by a prime

√

that is at most k, and by proving by induction on n that at the beginning

of the nth iteration of the main loop, A[i] = 0 i¬ i is divisible by a prime

less than n, for i = n, . . . , k. We leave the details of this to the reader.

We are more interested in the running time of the algorithm. To analyze

the running time, we assume that all arithmetic operations take constant

time; this is reasonable, since all the quantities computed in the algorithm

are bounded by k, and we need to at least be able to index all entries of the

array A, which has size k.

Every time we execute the inner loop of the algorithm, we perform O(k/n)

steps to clear the entries of A indexed by multiples of n. Naively, we could

bound the running time by a constant times

k/n,

√

n¤ k

86 The distribution of primes

which is O(k len(k)), where we have used a little calculus (see §A2) to derive

that

dy

+ O(1) ∼ log .

1/n =

y

1

n=1

However, the inner loop is executed only for prime values of n; thus, the

running time is proportional to

k/p,

√

p¤ k

and so by Theorem 5.10 is ˜(k len(len(k))).

Exercise 5.16. Give a detailed proof of the correctness of the above algo-

rithm.

Exercise 5.17. One drawback of the above algorithm is its use of space:

it requires an array of size k. Show how to modify the algorithm, without

substantially increasing its running time, so that one can enumerate all the

√

primes up to k, using an auxiliary array of size just O( k).

Exercise 5.18. Design and analyze an algorithm that on input k outputs

the table of values „ (n) for n = 1, . . . , k, where „ (n) is the number of positive

divisors of n. Your algorithm should run in time O(k len(k)).

5.5 The prime number theorem . . . and beyond

In this section, we survey a number of theorems and conjectures related to

the distribution of primes. This is a vast area of mathematical research,

with a number of very deep results. We shall be stating a number of theo-

rems from the literature in this section without proof; while our intent is to

keep the text as self contained as possible, and to avoid degenerating into

“mathematical tourism,” it nevertheless is a good idea to occasionally have

a somewhat broader perspective. In the following chapters, we shall not

make any critical use of the theorems in this section.

5.5.1 The prime number theorem

The main theorem in the theory of the density of primes is the following.

Theorem 5.14 (Prime number theorem). We have

π(x) ∼ x/ log x.

5.5 The prime number theorem . . . and beyond 87

Proof. Literature”see §5.6. 2

As we saw in Exercise 5.12, if π(x)/(x/ log x) tends to a limit as x ’ ∞,

then the limit must be 1, so in fact the hard part of proving the prime

number theorem is to show that π(x)/(x/ log x) does indeed tend to some

limit.

One simple consequence of the prime number theorem, together with The-

orem 5.4, is the following:

Theorem 5.15. We have

‘(x) ∼ x.

Exercise 5.19. Using the prime number theorem, show that pn ∼ n log n,

where pn denotes the nth prime.

Exercise 5.20. Using the prime number theorem, show that Bertrand™s

postulate can be strengthened (asymptotically) as follows: for all > 0,

there exist positive constants c and x0 , such that for all x ≥ x0 , we have

x

π((1 + )x) ’ π(x) ≥ c .

log x

5.5.2 The error term in the prime number theorem

The prime number theorem says that

|π(x) ’ x/ log x| ¤ δ(x),

where δ(x) = o(x/ log x). A natural question is: how small is the “error

term” δ(x)? It turns out that:

Theorem 5.16. We have

π(x) = x/ log x + O(x/(log x)2 ).

This bound on the error term is not very impressive. The reason is that

x/ log x is not really the best “simple” function that approximates π(x). It

turns out that a better approximation to π(x) is the logarithmic integral,

de¬ned for real x ≥ 2 by

x

dt

li(x) := .

log t

2

It is not hard to show (see Exercise 5.8) that

li(x) = x/ log x + O(x/(log x)2 ).

88 The distribution of primes

Table 5.2. Values of π(x), li(x), and x/ log x

x π(x) li(x) x/ log x

103 168 176.6 144.8

106 78498 78626.5 72382.4

109 50847534 50849233.9 48254942.4

1012 37607912018 37607950279.8 36191206825.3

1015 29844570422669 29844571475286.5 28952965460216.8

1018 24739954287740860 24739954309690414.0 24127471216847323.8

Thus, li(x) ∼ x/ log x ∼ π(x). However, the error term in the approximation

of π(x) by li(x) is much better. This is illustrated numerically in Table 5.2;

for example, at x = 1018 , li(x) approximates π(x) with a relative error just

under 10’9 , while x/ log x approximates π(x) with a relative error of about

0.025.

The sharpest proven result is the following:

Theorem 5.17. Let κ(x) := (log x)3/5 (log log x)’1/5 . Then for some c > 0,

we have

π(x) = li(x) + O(xe’cκ(x) ).

Proof. Literature”see §5.6. 2