Sieve of Eratosthenes: Prime Finding Algorithm Explained

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit n. Instead of testing each number individually, you write down all numbers from 2 to n and systematically cross out the multiples of each prime — whatever remains uncrossed is prime.

It matters because it is the fastest simple way to generate a complete prime table up to millions, and it teaches a key algorithmic idea: eliminating composites in bulk is far cheaper than testing primality one number at a time.

Key Concepts

• Sieving: crossing out multiples of each discovered prime, starting from p squared (smaller multiples were already crossed by smaller primes).
• Stopping rule: you only need to sieve with primes p ≤ √n; any remaining uncrossed number must be prime.
• Time complexity: about n log log n operations — nearly linear, much faster than trial-dividing every number.
• 1 is crossed out first: it is neither prime nor composite, so it never survives.

How It Works

1. List integers from 2 to n; cross out 1 immediately.
2. Take the smallest uncrossed number p — it is prime. Cross out all multiples of p from p squared upward.
3. Repeat step 2 with the next uncrossed number.
4. Stop once p > √n. Every number still uncrossed is prime.
5. Why it works: any composite ≤ n has a prime factor ≤ √n, so it gets crossed out by that factor's pass.

Worked Example

Find all primes up to 30. List 2–30, cross out 1. p = 2: cross 4, 6, 8, up to 30. p = 3: cross 9, 15, 21, 27 (6, 12 and the rest already gone). p = 5: cross 25 (10, 15, 20 already gone). Next uncrossed is 7, but 7 > √30 ≈ 5.48, so stop. Survivors: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — ten primes. Check: 27 = 3 times 9 was crossed, and 29 has no divisor ≤ 5, confirming it is prime.

Common Misconceptions

• "You must sieve with every prime up to n." Stopping at √n is enough — beyond that, p squared exceeds n, so there is nothing new to cross out.
• "Crossing starts at 2p." Start at p squared; multiples like 2p, 3p were already crossed by smaller primes, so beginning earlier wastes work.
• "The sieve tests each number." It never tests — it marks. The primes are simply the numbers nobody marked.

Real-World Applications

• Generating prime tables for cryptography setup and number-theory software.
• Competitive programming: pre-sieving to a million answers thousands of prime queries instantly.
• Teaching: the classic first example of an algorithm trading memory (the list) for speed.

The Sieve of Eratosthenes finds every prime up to n by crossing out multiples of each prime up to √n, starting each pass at p squared. What survives is prime — a 2,300-year-old algorithm still running in modern code.