Unmarked
Current Prime
Confirmed Prime
Composite (crossed out)
🔢 Sieve of Eratosthenes
An ancient algorithm for finding all prime numbers up to a given limit N. Starting from 2, mark all multiples of each prime as composite. Numbers that survive all sweeps are prime.
Time Complexity: O(n log log n) — nearly linear, extremely efficient.
Space Complexity: O(n) — one boolean per number.
Key Insight: We only need to check primes up to √N, because any composite ≤ N must have a factor ≤ √N.