AlgoScope

Segmented Sieve

Sieve a large range in cache-sized blocks using primes up to sqrt(high).

Mathematics, algorithm, advanced
2 crosses out 15 numbers from 100.100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129

Sieve of Eratosthenes: A window high up the number line

Decision, step 2 of 8

Prime 2: 100 divided by 2 rounds up to 100, so that is the first multiple of 2 in the window. Cross out 100 and every 2 after it: 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128.

How sieve of eratosthenes works

Cost

Best
O(n log log n)
Average
O(n log log n)
Worst
O(n log log n)
Space
O(sqrt(n) + block)

Taught by the same lesson

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