Legendre sieve
Encyclopedia
In mathematics
, the Legendre sieve, named after Adrien-Marie Legendre
, is the simplest method in modern sieve theory
. It applies the concept of the Sieve of Eratosthenes
to find upper or lower bound
s on the number of prime
s within a given set of integers. Because it is a simple extension of Eratosthenes
' idea, it is sometimes called the Legendre–Eratosthenes sieve.
where A is a set of integers, P is a product of distinct primes,
is the Möbius function
, and
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:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Legendre sieve, named after Adrien-Marie Legendre
Adrien-Marie Legendre
Adrien-Marie Legendre was a French mathematician.The Moon crater Legendre is named after him.- Life :...
, is the simplest method in modern sieve theory
Sieve theory
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. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...
. It applies the concept of the Sieve of Eratosthenes
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
to find upper or lower bound
Upper bound
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
s on the number of prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s within a given set of integers. Because it is a simple extension of Eratosthenes
Eratosthenes
Eratosthenes of Cyrene was a Greek mathematician, poet, athlete, geographer, astronomer, and music theorist.He was the first person to use the word "geography" and invented the discipline of geography as we understand it...
' idea, it is sometimes called the Legendre–Eratosthenes sieve.
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 functionMöbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...
, and
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
denotes the floor functionFloor functionIn mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...
). 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
(where 
denotes the number of primes below z) combinations of primes have been covered.
Once S(A, P) has been calculated for this special case, it can be used to bound
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 sieveBrun sieveIn the field of number theory, the Brun sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences...
and Selberg sieveSelberg sieveIn mathematics, in the field of number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences...
. 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.