Algorithm (Eratosthenes, ~240 BC):
For each prime p, mark all
multiples p², p²+p, p²+2p,…
Time: O(N log log N)
Space: O(N)
π(N) ~ N/ln(N) (PNT, 1896)
Current prime: —
Primes found: 0
π(N)/predicted: —
Gold = prime
Red = composite (sieved)
Dark = unchecked