It applies the concept of the Sieve of Eratosthenes to find upper or lower bounds on the number of primes within a given set of integers.
Because it is a simple extension of Eratosthenes' idea, it is sometimes called the Legendre–Eratosthenes sieve.
[1] The central idea of the method is expressed by the following identity, sometimes called the Legendre identity: where A is a set of integers, P is a product of distinct primes,
is the set of integers in A divisible by d, and S(A, P) is defined to be: i.e. S(A, P) is the count of numbers in A with no factors common with P. Note that in the most typical case, A is all integers less than or equal to some real number X, P is the product of all primes less than or equal to some integer z < X, and then the Legendre identity becomes: (where
In this example the fact that the Legendre identity is derived from the Sieve of Eratosthenes is clear: the first term is the number of integers below X, the second term removes the multiples of all primes, the third term adds back the multiples of two primes (which were miscounted by being "crossed out twice") but also adds back the multiples of three primes once too many, and so on until all
The Legendre sieve has a problem with fractional parts of terms accumulating into a large error, which means the sieve only gives very weak bounds in most cases.