The ancient algorithm for finding all primes up to N
Press Start to begin the sieve.
Eratosthenes of Cyrene (~276–194 BCE) devised this elegant algorithm.
Starting at 2, mark all multiples as composite. The next unmarked number is prime — repeat.
You only need to check up to sqrt(N) because any composite number up to N must have a factor at or below sqrt(N).
Time complexity is O(N log log N). The prime counting function pi(N) ~ N/ln(N) (Prime Number Theorem).