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 $𝒜$ that are not divisible by 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) is the characteristic function (http://planetmath.org/CharacteristicFunction) of the set of numbers that are not divisible 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 any primes 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 primes less than $x$ we set $𝒜=\{y,y+1,\mathrm{\dots },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

$\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 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].

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