1.7. Notes 27

Elementary Methods in the Analytic Theory of Numbers by A. O. Gel-

fond and Y. V. Linnik is a classic that covers some of the material of this

chapter in greater depth, and other topics as well. Elementary methods in

number theory by M. B. Nathanson and Not Always Buried Deep by P. Pol-

lack also treat elementary techniques in analytic number theory. Material

of this kind may also be found in Introduction to the Theory of Numbers

by G. H. Hardy and E. M. Wright, Lectures on Elementary Number Theory

by Hans Rademacher, and Introduction to the Theory of Numbers by H. N.

Shapiro.

1.7. Notes

Gauss never published his empirical investigations on the distribution of the primes,

but these are known from a letter that he wrote on Christmas Eve of 1849 to a

former student of his, the astronomer J. F. F. Encke, and also from cryptic jottings

in his research diary and on a flyleaf of a logarithm table. See pages 444–447 of

volume II and pages 11–18 of volume X of his collected works [Gau33].

Legendre published the prime factorization of the factorial in the 1808 edition

of his treatise Essai sur la Th´ eorie des Nombres [Leg08]. There he also proposed

π(x) ≈

x

log(x) − 1.08366

as an excellent approximation. Today it is known that li(x) is a much better

approximation for very large x, and that the asymptotically best approximation to

π(x) of the form x/(log(x)−A) is obtained for A = 1. But Legendre’s approximation

is better than Gauss’ approximation in the interval between x =

102

and x =

4·106, which stretches beyond the range of the tables of primes available in the

early nineteenth century. Gauss makes a comment in his letter to Encke on the

approximation of Legendre, to the effect that he does not care to commit himself

as to what limit A(x) in

π(x) =

x

log(x) − A(x)

,

may tend to as x → +∞.

Legendre made yet a third discovery of great importance to the development of

prime number theory. Since antiquity an algorithm had been known for eﬃciently

constructing tables of primes. The algorithm is called the Sieve of Eratosthenes,

after the Hellenistic scholar Eratosthenes of Cyrene. We will explain how his al-

gorithm may be used to construct a table of primes up to 30. Start with a list of

the integers n with 2 ≤ n ≤ 30. Keep the integer 2 but strike out all its proper

multiples. Then keep the next integer 3, but strike out all its proper multiples.

Next keep 5, but strike out all its proper multiples. The integers left in the list are

the primes 2 ≤ p ≤ 30. For every composite integer n ≤ 30 has some prime divisor

p ≤

√

30 5.5. Note that we obtain the primes in the interval [6, 30] by remov-

ing from the set of integers in that interval those that lie in the three arithmetic

progressions 2Z, 3Z and 5Z. Legendre reformulated the Sieve of Eratosthenes in

terms of the principle of exclusion and inclusion from combinatorics, potentially