= Sieve of Eratosthenes
{wiki}
= Eratosthenes sieve
{c}
{synonym}
The <sieve of Eratosthenes> finds all <prime numbers> at most an <integer> $N\geq2$. Start with the <integers> $2,\ldots,N$ marked as candidates. For each surviving candidate $p$ in increasing order, mark the multiples $p^2,p^2+p,\ldots$ up to $N$ as <composite numbers>. Stop processing candidates once $p^2>N$: the surviving candidates are exactly the <prime numbers>. Starting at $p^2$ saves work because any smaller proper multiple of $p$ already has a smaller <prime factor>. https://web.stanford.edu/class/cs106aj/res/handouts/36-Section-6.pdf[Jerry Cain, Stanford CS106AJ, Section Handout 6, Problem 4: the sieve of Eratosthenes]{ref}.
For a complete run with $N=60$, the only <prime numbers> at most $\sqrt{60}$ are $2,3,5,7$, since $7^2\leq60<8^2$. Exclude one before starting; it is not a <prime number>. The four marking passes are:
* $p=2$: mark $4,6,8,\ldots,60$, removing 29 candidates.
* $p=3$: mark $9,12,15,\ldots,60$. The nine newly removed candidates are $9,15,21,27,33,39,45,51,57$; the <even integers> were already marked.
* $p=5$: mark $25,30,35,40,45,50,55,60$. Only $25,35,55$ are newly removed.
* $p=7$: mark $49,56$. Only $49$ is newly removed.
There are $59-29-9-3-1=17$ surviving <prime numbers>:
$$
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59.
$$
The next surviving candidate is $11$, and $11^2>60$, so no further marking pass is necessary. A <prime number> used for marking remains a candidate: starting at $p^2$ never marks $p$ itself.
\Image[/prime-sieve-steps.png]
{title=Four passes of the <sieve of Eratosthenes> through 60 leave seventeen <prime numbers>}
{description=Blue cells are newly marked <composite numbers>; gray cells were removed earlier. White cells are candidates in the first three panels, and green cells are the final <prime numbers>. The outlined cell identifies the <prime number> used for that pass. One is excluded throughout.}
The saving from starting at $p^2$ is justified by the smaller multiplier: if $p k<p^2$ with $2\leq k<p$, then $k$ has a <prime factor> $q<p$, so $q$ has already marked $p k$. For $p=7$, the earlier multiples $14,21,28,35,42$ have already been marked using $2,3$ or $5$. The first new possibility is $49$.
For $N=100$, only the <prime numbers> $2,3,5,7$ need marking passes. They remove all the <composite numbers>, leaving \b[25 <prime numbers>]. The diagram colors each <composite number> by its smallest <prime factor>, so it shows which marking pass removes it first. The excluded <integer> one is shown separately.
\Image[/prime-sieve-smallest-factors.png]
{title=The <sieve of Eratosthenes> leaves 25 <prime numbers> among the <integers> from one to 100}
{description=Each colored <composite number> is assigned to its smallest <prime factor>, one of $2,3,5,7$. The green survivors are <prime numbers>; one is neither a <prime number> nor a <composite number>.}
Why does the <algorithm> work? A surviving candidate cannot be a <composite number>, since its smaller <prime factor> would already have removed it. Conversely, marking proper multiples never removes a <prime number>. Every <composite number> at most $N$ has a <prime factor> at most $\sqrt N$, so no later pass is needed. The <sieve of Eratosthenes> is useful when an entire bounded list is wanted; <primality testing> of one large <integer> is a different computational task.
The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of \i[Introduction to Arithmetic], names Eratosthenes and describes separating <prime numbers> from <composite numbers> by marking multiples among the <odd integers> beginning with three. That passage documents the sieve tradition; the bounded <algorithm> above and its $p^2$ starting rule are the formulation explained here, rather than instructions quoted from <Euclid's Elements>. https://stoicheiamath.com/wp-content/uploads/2025/09/Nicomachus-Introduction-to-Arithmetic-Student-Edition.pdf#page=28[Nicomachus, Introduction to Arithmetic I.13.2–8, Martin Luther D'Ooge translation (1926), revised classroom edition by Nathanael Hahn (2025), pp. 24–25]{ref}
Back to article page
