# Sieve method

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A general method in number theory which generalizes the principle of sifting compound numbers from the natural series (see Eratosthenes, sieve of). The problem of the sieve method consists in evaluating for a finite set of integers the quantity of those elements that are not divisible by any prime number from some set of prime numbers. The "sifting" function , which denotes the number of such elements from under the additional condition , is often estimated by using information about the number of elements of a set . This set consists of the elements of that are divisible by a square-free number . When , . Therefore the more general sifting function is usually estimated.

The choice of an expected value for in the form , where is the expected value for and is a multiplicative function, is governed by the fact that the degree of error

should be relatively low. If, moreover, (at least "on the average" ), then is called the dimension of the sieve.

The most advanced branch of the general theory of the sieve method and its applications is that of the linear sieve (when ). There are various specializations, the most important of which are the Brun sieve and the Selberg sieve.

When the sieve method is applied to additive problems (see Additive number theory), the sifting function must be estimated from below as well as from above. Estimates from below may be based on the logical combinatorial identity

The most precise estimates from below are obtained by invoking combinatorial considerations associated with the use of weight functions. A strong result in the applications of the sieve method with weight functions is that each sufficiently large even number is representable in the form , where is a prime number and contains at most two prime factors.

#### References

 [1] K. Prachar, "Primzahlverteilung" , Springer (1957) [2] A.O. Gel'fond, Yu.V. Linnik, "Elementary methods in the analytic theory of numbers" , M.I.T. (1966) (Translated from Russian) [3] H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974)