What Is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is a classic algorithm that finds all primes from 2 to N at once. Instead of testing each number for primality, it crosses out every multiple of each prime it finds, filtering out the composites.
The one-line idea: "multiples of a prime are not prime." Sweep from small numbers, crossing out multiples, and whatever survives is prime.
How It Works
Step 1. Mark every number from 2 to N as a "prime candidate" (a boolean array of true).
Step 2. Start at p = 2. If p is still a candidate, cross out all its multiples p², p²+p, p²+2p, ... as "not prime".
Step 3. Increase p by 1 and repeat. Stop once p exceeds √N — larger composites have already been crossed out by smaller primes.
Step 4. The numbers still true at the end are all the primes ≤ N.
The AlgoNote visualization shows multiples being crossed off the grid in turn each time a prime is fixed, step by step.
Why Start Crossing at p²?
Multiples of p with a coefficient smaller than p (2p, 3p, ..., (p-1)p) have already been crossed out by smaller primes (2, 3, …). So the first new multiple to cross is p × p = p². This small optimization removes a lot of redundant work.
Likewise, if p > √N then p² > N, so there are no multiples left to cross within range — you can stop.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(N log log N) |
| Space | O(N) |
Nearly linear, computing primes up to the millions almost instantly.
Walking Through an Example
N = 20:
- •p=2: cross out 4, 6, 8, …, 20
- •p=3: cross out 9, 12, 15, 18
- •p=4: already crossed (skip)
- •p=5: 5 > √20 ≈ 4.47 → stop
- •survivors: 2, 3, 5, 7, 11, 13, 17, 19 → all prime
Common Mistakes
- •Crossing from 2p: not wrong, but less efficient than starting at
p². - •Off-by-one bounds: get the
p ≤ √Norp*p ≤ Ncondition exactly right. - •Handling 1: 1 is not prime, so exclude it from candidates from the start.
See It in Action on AlgoNote
Watch the multiples get crossed off the grid each time a prime is fixed, leaving only primes at the end, step by step on AlgoNote.