sieve of Eratosthenes

The sieve of Eratosthenes is the number-theoretic version of theprinciple of inclusion-exclusion. In the typical application ofthe sieve of Eratosthenes one is concerned with estimating thenumber of elements of a set $𝒜$ that are not divisibleby any of the primes in the set $𝒫$.

Möbius inversion formula (http://planetmath.org/MobiusInversionFormula) can be written as

(1)

If we set $P={\prod }_{p\in 𝒫}p$ then (1) isthe characteristic function (http://planetmath.org/CharacteristicFunction) of the set of numbers that are notdivisible by any of the primes in $𝒫$. If we set $A_d$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 anyprimes in $𝒫$ can be expressed as

$$\sum _{n\in 𝒜}\sum _{\begin{array}{c}d\mid n\\ d\mid P\end{array}}\mu (d)=\sum _{d\mid P}\mu (d)\sum _{\begin{array}{c}n\in 𝒜\\ d\mid n\end{array}}1=\sum _{d\mid P}\mu (d)A_d.$$(2)

Example. To establish an upper bound on the number of primesless than $x$ we set $𝒜=\{y,y+1,\mathrm{\dots },x\}$ and $P=\{p:p\text{ is a prime less than }y\}$. Then (2) countsthe number of integers between $y$ and $x$ that are not divisibleby any prime less than $y$. Hence the number of primes notexceeding $x$ is

$\pi (x)$$\le {\displaystyle \sum _{d\mid P}}\mu (d)\left((x-y)/d+O(1)\right)$

$\le x{\displaystyle \sum _{d\mid P}}{\displaystyle \frac{\mu (d)}{d}}+O(\left|P\right|)$

$=x{\displaystyle \prod _{p\le y}}(1-1/p)+O(2^y).$

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

$$x\frac{e^{-\gamma }+o(1)}{\log y},$$

where $\gamma$ is Euler’s constant. Setting $y=\frac{1}{2}\log x$we obtain

$$\pi (x)\le \left(e^{-\gamma }+o(1)\right)\frac{x}{\log \log x}.$$

The obtained bound is clearly inferior to the prime numbertheorem, but the method applies to problems that are not tractableby the other techniques.

The error term of the order $O(2^y)$ can be significantly reducedby using more robust sifting procedures such as Brun’s (http://planetmath.org/BrunsPureSieve) and Selberg’s sieves. For detailed expositionof various sieve methods see monographs[1, 2, 3].