title: Turán sieve
text: # 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. 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$ be 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
  
      $S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .$
  
  We assume that $|A_d|$ may be estimated, when d is a prime p by
  
      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): \left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}
  
  and when d is a product of two distinct primes d = p q by
  
      $\left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}$
  
  where X = |A| and f is a function with the property that 0 ≤ f(d) ≤ 1. Put
  
      $U(z)=\sum _{p\mid P(z)}f(p).$
  
  Then
  
      $S(A,P,z)\leq {\frac {X}{U(z)}}+{\frac {2}{U(z)}}\sum _{p\mid P(z)}\left\vert R_{p}\right\vert +{\frac {1}{U(z)^{2}}}\sum _{p,q\mid P(z)}\left\vert R_{p,q}\right\vert .$
  
  ## 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.
  