## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required