In the field of number theory, the Brun sieve (also called Brun's pure 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.
It was developed by Viggo Brun in 1915 and later generalized to the fundamental lemma of sieve theory by others.
In terms of sieve theory the Brun sieve is of combinatorial type; that is, it derives from a careful use of the inclusion–exclusion principle.
be a finite set of positive integers.
be some set of prime numbers.
For each prime
denote the set of elements of
that are divisible by
This notation can be extended to other integers
that are products of distinct primes in
In this case, define
to be the intersection of the sets
for the prime factors
Finally, define
be an arbitrary positive real number.
The object of the sieve is to estimate:
denotes the cardinality of a set
, which in this case is just its number of elements.
Suppose in addition that
may be estimated by
is some multiplicative function, and
is some error function.
This formulation is from Cojocaru & Murty, Theorem 6.1.2.
With the notation as above, suppose that Then
is the cardinal of
is any positive integer and the
invokes big O notation.
denote the maximum element in
for a suitably small
The last two results were superseded by Chen's theorem, and the second by Goldbach's weak conjecture (