Sieve of Eratosthenes
mediumTime: O(n log log n)Space: O(n)
Signals to notice
find all primes up to neliminate multiplessieve
Brute force first
Test each number for primality — O(n√n).
The key insight
Sieve of Eratosthenes: mark multiples of each prime starting from p². O(n log log n).
What must stay true
Every composite has a prime factor ≤ √n. Marking multiples of primes up to √n eliminates all composites.
Easy way to go wrong
Starting elimination from 2p instead of p² — smaller multiples already marked by prior primes.