Segmented Sieve
Sieve a large range in cache-sized blocks using primes up to sqrt(high).
Decision · step 2 of 8Sieve 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.
What you will see
Blocks are sieved one at a time with the same small prime list.
Cost
| Best | O(n log log n) |
|---|---|
| Average | O(n log log n) |
| Worst | O(n log log n) |
| Space | O(sqrt(n) + block) |
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.
Before this
Taught by the same lesson
Sieve of Eratosthenes covers these too, in the same run.