Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient and highly efficient algorithm for finding all prime numbers up to a given limit N. It works iteratively by marking the multiples of each prime, starting with 2. By only processing primes p where p² ≤ N and marking their multiples starting from p², the algorithm minimizes redundant work.

Experiment in the Module

Open the Sieve of Eratosthenes explorer to step through the marking process visually.

1. Set Limit N to 49 and click Reset to begin at the initial state.
2. Click Step to process p = 2. You will see 4, 6, 8, ... up to 48 marked as composites.
3. Click Step to process p = 3, marking its multiples starting from 9.
4. Click Step to process p = 5, marking its multiples starting from 25.
5. Click Step to process p = 7, marking its multiple 49 (which is exactly 7²).
6. The fourth pass completes the trace: the next unmarked prime is 11, and 11² > 49. Step is now disabled, and the 15 primes up to 49 are visible.
7. Click Reset to rewind the same Limit N, then Finish to reveal all four passes instantly.