Larger sieve
From Wikipedia, the free encyclopedia
In number theory, the larger sieve is a sieve invented by Patrick X. Gallagher. The name denotes a heightening of the large sieve. Combinatorial sieves like the Selberg sieve are strongest, when only a few residue classes are removed, while the term large sieve means that this sieve can take advantage of the removal of a large number of up to half of all residue classes. The larger sieve can exploit the deletion of an arbitrary number of classes.
Suppose that is a set of prime powers, N an integer, a set of integers in the interval [1, N], such that for there are at most residue classes modulo , which contain elements of .
Then we have
provided the denominator on the right is positive.[1]
