Sieve of Eratosthenes
mediumTime: O(n log log n)Space: O(n)
Recognize the pattern
find all primes up to neliminate multiplessieve
Brute force idea
Test each number for primality — O(n√n).
Better approach
Sieve of Eratosthenes: mark multiples of each prime starting from p². O(n log log n).
Key invariant
Every composite has a prime factor ≤ √n. Marking multiples of primes up to √n eliminates all composites.
Watch out for
Starting elimination from 2p instead of p² — smaller multiples already marked by prior primes.