Sieve of Eratosthenes: the idea
Prerequisites: Divisibility, multiples, and prime numbers.
A prime is an integer greater than one whose positive divisors are only one and itself. The sieve begins by treating every integer from 2 through N as a candidate. For each unmarked p with p² ≤ N, it marks multiples starting at p² as composite. Smaller multiples have already been reached by smaller prime factors. At the end, all remaining candidates are prime.
Try it
Use limit 50. Watch 2 remove even composites, then 3 remove multiples that remain, then 5 and 7. Before completion, a surviving cyan number is only a candidate; after completion, green certifies prime status.
Reading the display
Pink is the current multiple, amber is the prime whose multiples are being processed, faded cells are composite, and green at completion marks primes. The grid is responsive and wraps on narrow screens.
Time and memory
O(N log log N) marking work and O(N) storage. These bounds describe the sieve, excluding recorded playback copies.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
Efficient for listing many primes up to a limit. It allocates storage proportional to the limit; checking a single huge number calls for a different approach. One is not prime.
Continue exploring
- Euclidean algorithm — Find a greatest common divisor through successive remainders.
- Extended Euclidean algorithm — Find a GCD and coefficients explaining how the inputs produce it.
- Binary exponentiation — Build large powers by repeated squaring and halving.