16

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 ( ...

Start Free Trial

No credit card required