Sieve of Eratosthenes
- $(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 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