In mathematics, the Legendre sieve is the simplest method in modern sieve theory. 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. For other meanings of mathematics or math, see mathematics (disambiguation). ... Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. ... In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. ... In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

Legendre's identity

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 Möbius function, and A_d is the set of integers in A divisible by d, and S(A, P) is defined to be: The classical Möbius function is an important multiplicative function in number theory and combinatorics. ...

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:

S(A,P)

(where denotes the floor function). 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"), and so on until all 2^π(z) (where π(z) denotes the number of primes below z) combinations of primes have been covered. The floor and fractional part functions In mathematics, the floor function of a real number x, denoted or floor(x), is the largest integer less than or equal to x (formally, ). For example, floor(2. ...

Once S(A,P) has been calculated for this special case, it can be used to bound π(X) using the expression

which follows immediately from the definition of S(A,P).

Problems

Unfortunately, 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. For this reason it is almost never used in practice, having been superseded by other techniques such as the Brun sieve and Selberg sieve. However, since these more powerful sieves are extensions of the basic ideas of the Legendre sieve, it is useful to first understand how this sieve works.