Brun’s pure sieve

In the first quarter of the twentieth century Viggo Brun developed an extensionPlanetmathPlanetmath of the sieve of EratosthenesMathworldPlanetmathPlanetmath that yielded good estimates on the number of elements of a set 𝒜 that are not divisible ( by any of the primes p1,,pk provided only that 𝒜 is “sufficiently regularly distributed” modulo these primes. That allowed him to prove that the sum of reciprocals of twin primesMathworldPlanetmath converges (the limit is now known as Brun’s constant), and that every sufficiently large even numberMathworldPlanetmath is a sum of two numbers each having at most 9 prime factorsMathworldPlanetmath. In what follows we describe the simplest form of Brun’s sieve, known as Brun’s pure sieve.

The sieve of Eratosthenes ( is based on the principle of inclusion-exclusion in the form

n𝒜p1npkn1 =n𝒜(n,p1pk)=11=n𝒜d(n,p1pk)μ(d)
=A1-pp1pkAp+pqp1pkApq+. (1)

Brun’s sieve is based on the observation that the partial sums of (1) alternatively overcount and undercount the number of elements of 𝒜 counted by the left side, that is,

dp1pkν(d)2h-1μ(d)Adn𝒜p1npkn1dp1pkν(d)2hμ(d)Ad (2)

where ν(d) denotes the number of prime ( factors of d. In applications Ad can usually be approximated by a multiple of a multiplicative function, that is,


where w(d) is some multiplicative function of d, and Rd is small compared to Xw(d)/d. Then the estimate in (2) takes the form

dp1pkν(d)tμ(d)Ad =dp1pkν(d)tμ(d)(Xw(d)/d+Rd)
=Xdp1pkν(d)tμ(d)w(d)d+O(dp1pkν(d)tRd) (3)

If the truncated sum is a good approximation to the full sum, then this formulaMathworldPlanetmath is an improvement over the sieve of Eratosthenes ( because the sum over error terms Rd is shorter.

Since uν(d)-t is greater than 1 for every u>1 and every d such that ν(d)>t, we have that

dp1pkν(d)tμ(d)w(d)d =dp1pkμ(d)w(d)d+O(dp1pkν(d)>tw(d)d)
and since the sum of a multiplicative function can be written as an Euler productMathworldPlanetmath, we get
to minimize the error term we choose u=t/p𝒫log(1+w(p)p), and get

Combining this with (3) and (2) we obtain

n𝒜p1npkn1=Xp𝒫(1-w(p)p)+XO(1tp𝒫w(p)p)t+O(dp1pkν(d)tRd) (4)

provided that u=t/p𝒫log(1+w(p)p)1.

Example. (Upper boundMathworldPlanetmath on the number of primes.) If we set 𝒫 to be all the primes less y, and 𝒜={1,2,,x}, then the right hand side of (4) provides an upper bound for the number of primes between y and x.

We have that w(d)=1 and Rd1. The second error term in (4) has at most yt summands, and the first error term is bounded by (ctloglogy)t by Merten’s theorem. Thus, the estimate (4) becomes


In order to squeeze out the best upper bound on the number of primes not exceeding x we have to minimize the right side of the inequalityMathworldPlanetmath above. The nearly optimal choice is t=cloglogx, and y=x1/2cloglogx for a sufficiently large constant c. With this choice we obtain


This inequality is stronger than the one obtained by an application of the sieve of Eratosthenes (

Example. (Upper bound on the number of twin primes.) If p<n and pn(n+2), then the integers n and n+2 cannot both be primes. Let 𝒫 be as above, and set 𝒜={n(n+1):n[y..x]}. Then w(2)=1, and w(p)=2 if p>2. The remainder Rd does not exceed 2ν(d). Like above we obtain


where π2(x) denotes the number of twin primes not exceeding x. Upon setting t=cloglogx, and y=x1/2cloglogx we obtain


This is the original result for which Viggo Brun developed the sieve now bearing his name. This result can be put in following striking form:


The sum

p,p+2 primes(1p+1p+2)


General combinatorial sieve

The inequality (2) was based on the observation that

dnμ(d)χ-(d)dnμ(d)dnμ(d)χ+(d) (5)

where χ- is the characteristic functionMathworldPlanetmathPlanetmathPlanetmath of the set of integers with no more than 2h-1 prime factors, and χ+ is the characteristic function of the set of integers with no more than 2h prime factors. It is possible to choose different functions χ- and χ+ that satisfy the inequality (5) to obtain bounds similar to (4). The problem of optimal choice of these functions in general is very hard. For more detailed information on Brun’s sieve and sieves in general one should consult the 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.
  • 4 Gérald Tenenbaum. Introduction to AnalyticPlanetmathPlanetmath and Probabilistic Number Theory, volume 46 of Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press. 0831.11001.
Title Brun’s pure sieve
Canonical name BrunsPureSieve
Date of creation 2013-03-22 14:10:54
Last modified on 2013-03-22 14:10:54
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 11
Author bbukh (348)
Entry type Topic
Classification msc 11N36
Classification msc 11N35
Related topic PrincipleOfInclusionExclusion
Related topic SieveOfEratosthenes2
Related topic BrunsConstant
Related topic BonferroniInequalities
Defines combinatorial sieve