The Sieve of Eratosthenes
What you'll learn: You'll master an ancient, elegant algorithm that finds all prime numbers up to any limit by systematically crossing out composites.
The Core Idea
The Sieve of Eratosthenes, dating back to ancient Greece (~240 BCE), is a surprisingly efficient way to generate all primes up to a given number n. Instead of testing each number individually for primality (as in trial division), the sieve works by elimination: start with all candidates, then cross out multiples of each prime as you discover them.
Think of it like a talent show: everyone starts on stage, but as you identify each "star performer" (prime), you remove all their "backup dancers" (multiples) from consideration.
How It Works
- List all integers from 2 to n.
- Start with the smallest unmarked number (initially 2). This is prime.
- Cross out all proper multiples of that prime (2×2, 2×3, 2×4, ...).
- Move to the next unmarked number and repeat steps 2–3.
- Stop when you reach √n—any remaining unmarked numbers are prime.
Why stop at √n? Because any composite number ≤ n must have at least one prime factor ≤ √n. Once you've sieved with all primes up to √n, only primes remain.
Example: Finding Primes ≤ 30
Start: 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 30
After sieving with 2: 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
After sieving with 3: 2, 3, 5, 7, 9, 11, 13, ...
After sieving with 5 (√30 ≈ 5.5): done!
Primes ≤ 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Key Takeaway: The Sieve of Eratosthenes efficiently finds all primes up to n by eliminating composites through successive marking of multiples, leveraging the fact that every composite has a prime factor ≤ √n.