Sieve theory

Sieve theory is a collection of methods for estimating sets of integers by removing those divisible by selected primes. It provides tools for studying primes and other integers defined by divisibility conditions.

Sieve of Eratosthenes: An algorithm that finds primes up to a bound by repeatedly removing multiples of each smallest remaining prime. The classical model: it removes multiples directly to isolate primes.
Arithmetic progression: A sequence of integers with a fixed difference between consecutive terms. Sieve conditions often remove specified residue classes modulo each prime.
Twin prime conjecture: The conjecture that infinitely many prime pairs differ by two. Sieve methods give strong bounds on twin-prime counts but cannot isolate prime pairs alone.
Brun sieve: A combinatorial sieve method using carefully chosen weights to bound sets avoiding specified prime divisors. It is a foundational combinatorial approach, exemplified by Brun's theorem.
Parity problem in sieve theory: A limitation of standard sieve methods that makes numbers with an even or odd number of prime factors difficult to distinguish. It blocks direct separation of primes from certain almost primes in many sieve problems.
Inclusion–exclusion principle: A counting identity that corrects sums over overlapping sets by alternating additions and subtractions of intersections. Sieve estimates begin with inclusion–exclusion over divisibility conditions.
Prime number: A natural number greater than one whose only positive divisors are one and itself. Primes are the divisors whose multiples the sieve removes.
Chen's theorem: A theorem stating that every sufficiently large even integer is the sum of a prime and a number with at most two prime factors. Chen combined sieve methods with analytic estimates to approach the Goldbach conjecture.
Selberg sieve: A sieve method that obtains upper bounds by minimizing a quadratic form in divisor weights. It often gives sharper upper bounds than elementary inclusion–exclusion truncations.
Prime k-tuples conjecture: A conjecture that every admissible finite pattern of linear forms contains infinitely many simultaneous primes. Its unresolved cases illustrate the limits of sieve methods alone.

Linked from 16 pages