Sieve of Eratosthenes

From ProofWiki
Jump to navigation Jump to search

Algorithm

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


Proof

The above constitutes an algorithm, for the following reasons:


Finiteness

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).


Definiteness

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


Inputs

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


Outputs

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


Effective

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: cited in 1981: William F. Clocksin and Christopher S. Mellish: Programming in Prolog.


Historical Note

The Sieve of Eratosthenes dates back to circa $\text {250}$$\text { BCE}$, and is attributed to Eratosthenes of Cyrene.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sieve_of_Eratosthenes&oldid=728504"