Turán sieve

In 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.

The result gives an upper bound for the size of the sifted set.

For each p in P, let Ap denote the set of elements of A divisible by p and extend this to let Ad be the intersection of the Ap for p dividing d, when d is a product of distinct primes from P. Further let A1 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 |Ad| 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.