# Turan sieve

In mathematics, in the field of number theory, the **Turán 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 Pál Turán in 1934.

## Description

In terms of sieve theory the Turán sieve is of *combinatorial type*: deriving from a rudimentary form of the inclusion-exclusion principle. The result gives an *upper bound* for the size of the sifted set.

Let *A* be a set of positive integers ≤ *x* and let *P* be a set of primes. For each *p* in *P*, let *A*_{p} denote the set of elements of *A* divisible by *p* and extend this to let *A*_{d} the intersection of the *A*_{p} for *p* dividing *d*, when *d* is a product of distinct primes from *P*. Further let A_{1} denote *A* itself. Let *z* be a positive real number and *P*(*z*) denote the product of the primes in *P* which are ≤ *z*. The object of the sieve is to estimate

We assume that |*A*_{d}| may be estimated, when *d* is a prime *p* by

and when *d* is a product of two distinct primes *d* = *p* *q* by

where *X* = |*A*| and *f* is a function with the property that 0 ≤ *f*(*d*) ≤ 1. Put

Then

## Applications

- The Hardy–Ramanujan theorem that the normal order of ω(
*n*), the number of distinct prime factors of a number*n*, is log(log(*n*)); - Almost all integer polynomials (taken in order of height) are irreducible.

## References

- Alina Carmen Cojocaru; M. Ram Murty.
*An introduction to sieve methods and their applications*. Cambridge University Press, 47-62. ISBN 0-521-61275-6. - George Greaves (2001).
*Sieves in number theory*. Springer-Verlag. ISBN 3-540-41647-1. - Heini Halberstam; H.E. Richert (1974).
*Sieve Methods*. Academic Press. ISBN 0-12-318250-6. - Christopher Hooley (1976).
*Applications of sieve methods to the theory of numbers*. Cambridge University Press, 21. ISBN 0-521-20915-3.