Sieve of Eratosthenes
Mark multiples of each prime; what survives is prime.
Decision · step 2 of 7Sieve of Eratosthenes: Primes up to 30
2 is still unmarked, so no smaller number divides it: prime. Cross out its multiples from 4 on: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30. Smaller multiples like 4 were already crossed by a smaller prime.
What you will see
A grid of numbers; each prime's multiples get crossed out in a sweep; primes remain lit.
Cost
| Best | O(n log log n) |
|---|---|
| Average | O(n log log n) |
| Worst | O(n log log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, run it on your own input.
Screen readers: Numbers announce their value and role; each step announces the arithmetic performed.
Reduced motion: Values crossfade; no travelling digits.