CONCEPT · Master
Sieve of Eratosthenes
also eratosthenes · SPF · primes
Mark composites up to n in O(n log log n). A smallest-prime-factor table then factors any k ≤ n in O(log k).
Intuition
Every composite has a prime factor ≤ √n. Mark from p²; smaller multiples already died.
When to reach for it
- Count / list primes ≤ n for n ≤ 1e7
- Many factorizations of values ≤ n
- Prefix counts of primes, totient sieve
Usual pits
- Trial division per query at n=1e6, q=1e5
- Primes < n vs ≤ n off-by-one
- Sieve of 1e12 — you meant √n or a segment sieve
- Starting the inner loop at 2p is correct but slower, not wrong