PlanetMath: sieve of Eratosthenes

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (231)
Orphanage
Unclass'd
Unproven (514)
Corrections (24)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

sieve of Eratosthenes

(Definition)

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}$ .

Möbius inversion formula can be written as

$\displaystyle \sum_{\substack{d\mid n\\ d\mid P}}\mu(d)=\sum_{d\mid \gcd(n,P)} ... ...)=\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 of the set of numbers that are not divisible by any of the primes in $\mathcal{P}$ . If we set to be the number of elements of that are divisible by , then the number of elements of that are not divisible by any primes in $\mathcal{P}$ can be expressed as

$\displaystyle \sum_{n\in\mathcal{A}}\sum_{\substack{d\mid n\\ d\mid P}}\mu(d)=\... ...d P}\mu(d)\sum_{\substack{n\in\mathcal{A}\\ d\mid n}}1=\sum_{d\mid P}\mu(d)A_d.$

(2)

Example. To establish an upper bound on the number of primes less than we set $\mathcal{A}=\{y,y+1,\dotsc,x\}$ and $P=\{p : p$ is a prime less than $y\}$ . Then (2) counts the number of integers between and that are not divisible by any prime less than . Hence the number of primes not exceeding 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

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

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

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

References

1: George Greaves.
Sieves in number theory.
Springer, 2001.
Zbl 1003.11044.
2: H. Halberstam and H.-E. Richert.
Sieve methods, volume 4 of London Mathematical Society Monographs.
1974.
Zbl 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.
Zbl 0327.10044.

"sieve of Eratosthenes" is owned by bbukh.

(view preamble | get metadata)

Log in to rate this entry.
(view current ratings)

Cross-references: reduced, prime number theorem, bound, Euler's constant, integers, upper bound, primes, divisible, number, application, principle of inclusion-exclusion
There are 3 references to this entry.

This is version 7 of sieve of Eratosthenes, born on 2004-01-24, modified 2006-09-05.
Object id is 5535, canonical name is SieveOfEratosthenes2.
Accessed 6697 times total.

Classification:

AMS MSC:

11N35 (Number theory :: Multiplicative number theory :: Sieves)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact