Sieve of Eratosthenes

From ProofWiki
Jump to navigation Jump to search


Take a set of natural numbers $S = \set {2, 3, 4, \ldots, n}$.

$(1): \quad$ Set $k = 2$.
$(2): \quad$ Delete from $S$ every multiple of $k$ (but not $k$ itself).
$(3): \quad$ Set $k$ equal to the smallest number of those remaining in $S$ greater than the current value of $k$.
$(4): \quad$ If $k \le \sqrt n$, go to step $(2)$. Otherwise, STOP.

What remains in $S$ is the complete set of all prime numbers less than or equal to $n$.


The above constitutes an algorithm, for the following reasons:


For each iteration through the algorithm, step $(3)$ is executed, which increases $k$ by at least 1.

The algorithm will terminate after at most $\sqrt n - 2$ iterations (and probably considerably less).


Step 1: Trivially definite.
Step 2: Trivially definite.
Step 3: Trivially definite.
Step 4: Trivially definite.


The input to this algorithm is the set of natural numbers $S = \set {2, 3, 4, \ldots, n}$.


The output to this algorithm is the set $S$ without any multiples of any numbers no greater than $\sqrt n$.

From Composite Number has Prime Factor not Greater Than its Square Root, it follows that all the numbers left in $S$ must be prime.

By the method of construction, no prime can have been deleted from $S$.

Hence the output consists of all, and only, the primes less than or equal to $n$.


Each step of the algorithm is basic enough to be done exactly and in a finite length of time.

Source of Name

This entry was named for Eratosthenes of Cyrene.

Sift the Two's and Sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.
-- Traditional [1]