Sieves
Sieve methods were created to attack the well-known Goldbach and twin-prime problems. Goldbach problem in strong form: is every reasonably large even number a sum of two prime numbers? Twin-prime problem: do pairs of consecutive odd numbers both prime, like 101 and 103, keep occurring forever? It turns out that there are excellent reasons why sieve methods alone cannot solve these problems, but they give partial information on these and many other problems where the `deeper' methods of analytic number theory, such as exponential sums will not work. For example pairs of consecutive odd numbers which are either prime or very hard to factorise do keep on occurring.
Sieve methods can be purely combinatorial like the "sieve of Eratosthenes", or partly combinatorial and partly analytic: finding an inequality by rearranging a sum of squares which must be positive - even the modulus squared of an exponential sum in the so-called "large sieve".
Sieving for prime numbers (sieve of Eratosthenes)
- Strike out all the multiples of 2 except 2 itself.
- The next number left after 2 is 3. Strike out all the multiples of 3 except 3 itself.
- The next number left after 3 is 5. Strike out all the multiples of 5 except 5 itself.
- The next number left after 5 is 7. Strike out all the multiples of 7 except 7 itself
You have now sieved by all the prime numbers up to 10.
The numbers that remain are 1 and the prime numbers up to 100.
References
- G. R. H. Greaves, Sieves in Number Theory, Springer 2001.
- M. N. Huxley, One-sided sifting density hypotheses in Selberg's sieve, Number theory (Turku, 1999), de Gruyter, Berlin, 2001, 105–114.
- G. R. H. Greaves, G. Harman, M. N. Huxley (ed), Sieves, Exponential Sums, and their Applications in Number Theory, Cambridge 1997.