A nightly job sieves every prime below 10^7. What dominates its cost, and what breaks at 10^9?

## Read the two costs separately A sieve has a **time** cost and a **space** cost, and interviewers ask this question because candidates reason about the first and forget the second. **Time** is Θ(n log log n) — the sum of `n/p` over primes `p <= n`, where the sum of `1/p` grows like `ln ln n`. The `log log` factor is effectively a small constant at any realistic scale, so the sieve is near-linear. Going from 10^7 to 10^9 multiplies the arithmetic by roughly 100 plus a whisker: tens of milliseconds becomes a few seconds. For a nightly batch job, that is nothing. **Space** is Θ(n) with a constant you choose, and it is the one that fails. The naive layout is one flag per candidate in the natural per-element size of a flag array, which on mainstream platforms is a byte: | ceiling | one byte per flag | one bit per flag | one bit, odds only | |---|---|---|---| | 10^7 | ~10 MB | ~1.25 MB | ~625 KB | | 10^8 | ~100 MB | ~12.5 MB | ~6 MB | | 10^9 | ~1 GB | ~125 MB | ~60 MB | At 10^7 every column is comfortable, which is exactly why the naive version ships. At 10^9 the first column is a gigabyte of resident memory for a batch job, and that is what breaks. This is one of the places where mainstream runtimes made visibly different calls on the same concept: some standard libraries offer a bit-packed sequence-of-booleans type while others store a full byte per element in the ordinary boolean array, so "one flag" costs 8x more in one ecosystem than another with identical source-level intent. Know which one you are on before you quote a memory number. ## The hidden second failure: cache Even when the array fits in RAM, the marking loop writes with stride `p`. For small primes the stride is tight and cache-friendly; for larger primes each write lands in a different cache line, and once the array exceeds last-level cache the job spends its time waiting on memory rather than computing. Measured throughput per candidate gets *worse* as `n` grows, even though the asymptotic bound says otherwise. This is the classic case of an asymptotically near-linear algorithm whose real-world constant is set by the memory hierarchy, and it is the strongest argument for segmentation independent of whether the array fits. ## The fixes, in order 1. **Bit-pack the flags.** One bit per candidate, index `i` living at word `i / 64` and bit `i % 64`. Eight times less memory, and eight times more candidates per cache line. The cost is slightly more work per access and code that is easier to get wrong. 2. **Store odd candidates only.** Every even number above 2 is composite, so index `i` can represent the value `2i + 1` and 2 is special-cased. Half the memory and half the marking work, at the price of an index mapping that must be right in both directions. 3. **Segment.** Sieve the base primes up to the square root of the ceiling with an ordinary small sieve — for a 10^9 ceiling that is primes below about 31,623, a few thousand of them, needing almost no memory. Then process the full range in windows sized to fit comfortably in cache; for each window, for each base prime, compute the first multiple inside the window and mark forward. Peak memory becomes the window plus the base primes rather than the whole range, and locality improves dramatically. Segmentation is also the only way to sieve a *high window* — say primes between 10^9 and 10^9 + 10^6 — without materialising everything below it. 4. **Do not precompute.** If the job actually tests a hundred specific values, a square-root trial division per value costs about 31,623 divisions each near 10^9 and needs zero memory. The sieve earns its array only when the query count is large relative to the range. ## How to answer this in an interview Say the two costs separately, then commit to a number. "Time is near-linear, so 10^9 is seconds — fine for a nightly job. Space is one flag per candidate, so a byte per flag is a gigabyte, and that is what breaks first. I would go bit-packed and odd-only, which lands around sixty megabytes, and if the ceiling keeps climbing or I only need a high window, segment it." That answer demonstrates the thing the question is actually probing: that you know a near-linear time bound does **not** mean an algorithm scales, because the resource that fails may be the other one. ## The trap to avoid The wrong answer is "`n log log n` is basically linear, so I would just raise the constant and let it run." It is technically true about the arithmetic and completely wrong about the job, which will be killed by the memory limit long before it finishes. The related wrong answer is reaching for a dynamic collection of discovered primes instead of a flat flag array — that replaces a compact bitmap with per-element overhead and pointer chasing, making the memory problem several times worse while also destroying locality.