Segmented Sieve
Sieve a large range in cache-sized blocks using primes up to sqrt(high).
Sieve of Eratosthenes: A window high up the number line
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.
Cost
- Best
- O(n log log n)
- Average
- O(n log log n)
- Worst
- O(n log log n)
- Space
- O(sqrt(n) + block)
Before this
Taught by the same lesson
Sieve of Eratosthenes covers these too, in the same run.