# sieve of Eratosthenes

The sieve of Eratosthenes   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 $\mathcal{A}$ that are not divisible by any of the primes in the set $\mathcal{P}$.

 $\sum_{\begin{subarray}{c}d\mid n\\ d\mid P\end{subarray}}\mu(d)=\sum_{d\mid\gcd(n,P)}\mu(d)=\begin{cases}1,&\text% {if }\gcd(n,P)=1,\\ 0,&\text{if }\gcd(n,P)>1.\end{cases}$ (1)

If we set $P=\prod_{p\in\mathcal{P}}p$ then (1) is the characteristic function    (http://planetmath.org/CharacteristicFunction) of the set of numbers that are not divisible by any of the primes in $\mathcal{P}$. 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 any primes in $\mathcal{P}$ can be expressed as

 $\sum_{n\in\mathcal{A}}\sum_{\begin{subarray}{c}d\mid n\\ d\mid P\end{subarray}}\mu(d)=\sum_{d\mid P}\mu(d)\sum_{\begin{subarray}{c}n\in% \mathcal{A}\\ d\mid n\end{subarray}}1=\sum_{d\mid P}\mu(d)A_{d}.$ (2)

Example. To establish an upper bound on the number of primes less than $x$ we set $\mathcal{A}=\{y,y+1,\ldots,x\}$ and $P=\{p:p\text{ 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

 $\displaystyle\pi(x)$ $\displaystyle\leq\sum_{d\mid P}\mu(d)\bigl{(}(x-y)/d+O(1)\bigr{)}$ $\displaystyle\leq x\sum_{d\mid P}\frac{\mu(d)}{d}+O(\left\lvert P\right\rvert)$ $\displaystyle=x\prod_{p\leq 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=\tfrac{1}{2}\log x$ we obtain

 $\pi(x)\leq\bigl{(}e^{-\gamma}+o(1)\bigr{)}\frac{x}{\log\log x}.$

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

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

## References

• 1 George Greaves. Springer, 2001. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=1003.11044Zbl 1003.11044.
• 2 H. Halberstam and H.-E. Richert. Sieve methods, volume 4 of London Mathematical Society Monographs. 1974. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0298.10026Zbl 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. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0327.10044Zbl 0327.10044.
Title sieve of Eratosthenes SieveOfEratosthenes1 2013-03-22 14:07:40 2013-03-22 14:07:40 bbukh (348) bbukh (348) 10 bbukh (348) Definition msc 11N35 PrincipleOfInclusionExclusion BrunsPureSieve