The sieve and circle methods
16.1 The Eratosthenes sieve
Eratosthenes observed in ancient Greek times that if, for a given x ≥ 1, one deletes from the natural numbers ≤ x all multiples of 2, of 3, of 5 and so on up to the largest prime ≤ √x then, apart from 1, only the primes between √x and x remain. This can be expressed by the following result usually attributed to Legendre.
Theorem 16.1 (Legendre’s formula) Let P denote the product of all primes ≤ √x. Then
Proof The theorem follows from the basic property of the Möbius function, that is, ∑d|n μ(d) is 0 if n > 1 and 1 if n = 1. Clearly π(x) − π(√x) + 1 is just the number of n ≤ x with ( ...