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 sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be. Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers. ... In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ... In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. ... In mathematics, the Legendre sieve is the simplest method in modern sieve theory. ... (19th century - 20th century - 21st century - more centuries) Decades: 1900s 1910s 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s The 20th century lasted from 1901 to 2000 in the Gregorian calendar (often from (1900 to 1999 in common usage). ...

One successful approach is to approximate a specific sifted set of numbers (e.g. the set of prime numbers) by another, simpler set (e.g. the set of almost prime numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves also do not work directly with sets per se, but instead count them according to carefully chosen weight functions on these sets (options for giving some elements of these sets more "weight" than others). In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ... In mathematics, a natural number n is called k_almost prime iff Ω(n) = k, where Ω(n) is the sum of the exponents in the prime decomposition of n: A natural number is thus prime iff it is 1-almost prime, and semiprime iff it is 2-almost prime. ... A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more of a weight than others. ...

Modern sieves include the Brun sieve, the Selberg sieve, and the large sieve. One of the original purposes of sieve theory was to try to prove conjectures in number theory such as the twin prime conjecture. While the original broad aims of sieve theory still are largely unachieved, there has been some partial successes, especially in combination with other number theoretic tools. Highlights include: In mathematics, the large sieve is a method of analytic number theory. ... The twin prime conjecture is a famous problem in number theory that involves prime numbers. ...

1. Brun's theorem, which asserts that the sum of the reciprocals of the twin primes converges (whereas the sum of the reciprocals of the primes themselves diverge);
2. Chen's theorem, which shows that there are infinitely many primes p such that p + 2 is either a prime or a semiprime (the product of two primes); a closely related theorem of Chen Jingrun asserts that every sufficiently large even number is the sum of a prime and another number which is either a prime or a semiprime. These can be considered to be near-misses to the twin prime conjecture and the Goldbach conjecture respectively.
3. The fundamental lemma of sieve theory, which (very roughly speaking) asserts that if one is sifting a set of N numbers, then one can accurately estimate the number of elements left in the sieve after N^ε iterations provided that ε is sufficiently small (fractions such as 1/10 are quite typical here). This lemma is usually too weak to sieve out primes (which generally require something like N^{1 / 2} iterations), but can be enough to obtain results regarding almost primes.
4. The Friedlander-Iwaniec theorem, which asserts that there are infinitely many primes of the form a² + b⁴.

The techniques of sieve theory can be quite powerful, but they seem to be limited by an obstacle known as the parity problem, which roughly speaking asserts that sieve theory methods have extreme difficulty distinguishing between numbers with an odd number of prime factors, and numbers with an even number of prime factors. This parity problem is still not very well understood. Chens theorem was first stated by Chinese mathematician Chen Jingrun in 1966, with further details of the proof in 1973. ... In mathematics, a semiprime (also called biprime or 2-almost prime) is a natural number that is the product of two (not necessarily distinct) prime numbers. ... Chen Jingrun (ch. ... In mathematics, the phrase sufficiently large is used in contexts such as: is true for sufficiently large which is actually shorthand for: there exists an such that is true for all . ... The twin prime conjecture is a famous problem in number theory that involves prime numbers. ... In mathematics, Goldbachs conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. ... In mathematics, a natural number n is called k_almost prime iff Ω(n) = k, where Ω(n) is the sum of the exponents in the prime decomposition of n: A natural number is thus prime iff it is 1-almost prime, and semiprime iff it is 2-almost prime. ...

Compared with other methods in number theory, sieve theory is comparatively elementary, in the sense that it does not necessarily require sophisticated concepts from either algebraic number theory or analytic number theory. Nevertheless, the more advanced sieves can still get very intricate and delicate (especially when combined with other deep techniques in number theory), and entire textbooks have been devoted to this single subfield of number theory; a classic reference is [1]. In mathematics, an algebraic number field (or simply number field) is a finite field extension of the rational numbers Q. That is, it is a field which contains Q and has finite dimension when considered as a vector space over Q. The study of algebraic number fields, and these days... Analytic number theory is the branch of number theory that uses methods from mathematical analysis. ...

Sieve theory is somewhat related to sieve algorithms such as the general number field sieve, used for factoring large numbers, although sieve theory and sieve algorithms serve different purposes. In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers. ...

References

• H. Halberstam and H. E. Richert. (1974). Sieve Methods. Academic Press, London, 1974. ISBN 0123182506.