sieve of Eratosthenes

The sieve of EratosthenesMathworldPlanetmathPlanetmath is the number-theoretic version of the principle of inclusion-exclusion. In the typical application of the sieve of Eratosthenes one is concerned with estimating the number of elements of a set 𝒜 that are not divisible by any of the primes in the set 𝒫.

Möbius inversion formulaMathworldPlanetmathPlanetmath ( can be written as

dndPμ(d)=dgcd(n,P)μ(d)={1,if gcd(n,P)=1,0,if gcd(n,P)>1. (1)

If we set P=p𝒫p then (1) is the characteristic functionMathworldPlanetmathPlanetmathPlanetmath ( of the set of numbers that are not divisible by any of the primes in 𝒫. If we set Ad to be the number of elements of A that are divisible by d, then the number of elements of A that are not divisible by any primes in 𝒫 can be expressed as

n𝒜dndPμ(d)=dPμ(d)n𝒜dn1=dPμ(d)Ad. (2)

Example. To establish an upper bound on the number of primes less than x we set 𝒜={y,y+1,,x} and P={p:p is a prime less than y}. Then (2) counts the number of integers between y and x that are not divisible by any prime less than y. Hence the number of primes not exceeding x is

π(x) dPμ(d)((x-y)/d+O(1))

By Mertens’ estimate for (1-1/p) the main term is


where γ is Euler’s constant. Setting y=12logx we obtain


The obtained bound is clearly inferior to the prime number theoremMathworldPlanetmath, but the method applies to problems that are not tractable by the other techniques.

The error term of the order O(2y) can be significantly reduced by using more robust sifting procedures such as Brun’s ( and Selberg’s sieves. For detailed exposition of various sieve methods see monographs [1, 2, 3].


  • 1 George Greaves. Sieves in number theoryMathworldPlanetmath. Springer, 2001. 1003.11044.
  • 2 H. Halberstam and H.-E. Richert. Sieve methods, volume 4 of London Mathematical Society Monographs. 1974. 0298.10026.
  • 3 C. Hooley. Application of sieve methods to the theory of numbers, volume 70 of Cambridge Tracts in Mathematics. Cambridge Univ. Press, 1976. 0327.10044.
Title sieve of Eratosthenes
Canonical name SieveOfEratosthenes1
Date of creation 2013-03-22 14:07:40
Last modified on 2013-03-22 14:07:40
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 10
Author bbukh (348)
Entry type Definition
Classification msc 11N35
Related topic PrincipleOfInclusionExclusion
Related topic BrunsPureSieve