# Sieve of Eratosthenes

## Contents

## 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
^{[1]}

- -- Traditional

## References

- ↑ Cited in 1981: William F. Clocksin and Christopher S. Mellish:
*Programming in Prolog*.

## Sources

- 1981: William F. Clocksin and Christopher S. Mellish:
*Programming in Prolog* - 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $33$ - 1992: George F. Simmons:
*Calculus Gems*... (previous) ... (next): Chapter $\text {B}.16$: The Sequence of Primes - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $33$