Sieve of Eratosthenes
Mark multiples of each prime. What survives is prime.
Sieve 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.
Cost
- Best
- O(n log log n)
- Average
- O(n log log n)
- Worst
- O(n log log n)
- Space
- O(n)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Sieve of Eratosthenes covers these too, in the same run.