AlgoScope

Sieve of Eratosthenes

Mark multiples of each prime. What survives is prime.

Mathematics, algorithm, beginner
2 is prime. 14 multiples are crossed out.123456789101112131415161718192021222324252627282930

Sieve of Eratosthenes: Primes up to 30

Decision, step 2 of 7

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)

Leads to

Topics that need this one first.

Taught by the same lesson

Sieve of Eratosthenes covers these too, in the same run.