Loading…

mediumMath GeometrySometimes asked

Segmented Sieve

Q: How do you solve Segmented Sieve using the Sieve Everything Up To R (Baseline) approach?

When to use it: Mention first to expose why the obvious idea fails — it anchors the memory problem the segmented sieve solves. The literal reading of 'primes in [L, R]' is: sieve all primes up to R the usual way, then keep the ones that land in the window. Allocate `isPrime[0..R]`, cross out multiples of each prime, and finally collect indices in `[L, R]`. **Why it is correct.** It is just the plain Sieve of Eratosthenes followed by a range filter. Correctness is inherited directly from the standard sieve: every composite ≤ R gets crossed out, every prime survives, and we report only those in `[L, R]`. **Why it does not ship.** The fatal flaw is space, not time. The boolean array has `R + 1` entries. With `R` around `10¹²` that is on the order of a terabyte of memory — the allocation fails before the algorithm even starts. Even when `R` is merely `10⁹`, you are burning a gigabyte to discard all but a thin slice of it. We are computing primality for `10¹²` numbers when the question only asked about the `10⁶` in the window. **The wasted-work insight.** Almost all of the array — every index outside `[L, R]` — is computed and then thrown away. That mismatch between work done and answer needed is the signal to segment: bring the sieve to the window instead of bringing the window to a full sieve. Time complexity: O(R log log R). Space complexity: O(R).

Math & Number Theory · 29 of 36 · 11 min

Given two integers L and R (with L ≤ R), return all prime numbers in the inclusive range [L, R] in increasing order.

The upper bound R can be as large as about 10¹², but the window width R − L is small (say up to 10⁶). A standard sieve sized to R would not fit in memory, so you must sieve the window directly using only the primes up to √R.

In plain English

We are not asked for all primes up to R — only those in a narrow band [L, R] that sits high on the number line. The key fact: if a number x ≤ R is composite, it has a prime factor at most √x ≤ √R. So the primes up to √R are enough 'erasers' to cross out every composite in the window. We sieve those base primes once with a plain sieve, then carry a boolean array indexed by offset from L and let each base prime cross out its multiples that fall inside [L, R].

Examples

Example 1

Input: L = 10, R = 20
Output: [11, 13, 17, 19]
Note: Base primes up to √20 ≈ 4 are {2, 3}. They cross out 10,12,14,16,18,20 (multiples of 2) and 12,15,18 (multiples of 3) inside the window; 11,13,17,19 survive.

Example 2

Input: L = 1, R = 10
Output: [2, 3, 5, 7]
Note: Same as a normal sieve over [1,10]; slot for 1 is cleared explicitly because no prime crosses it out.

Example 3

Input: L = 100, R = 110
Output: [101, 103, 107, 109]
Note: Base primes up to √110 ≈ 10 are {2,3,5,7}. After crossing out their multiples in [100,110], four primes remain.

Constraints

1 ≤ L ≤ R ≤ 10¹² (R is huge; R − L is the part that fits in memory)
0 ≤ R − L ≤ 10⁶ (window width — the boolean buffer is O(R − L))
Return primes in ascending order
L may equal 1 → 1 is not prime and must be excluded

Clarifying questions4First question: How large can R get, and how wide is the window R − L?Explore questions

Q1.How large can R get, and how wide is the window R − L?
R can be ~10¹² (too big to sieve directly), but R − L fits in memory (≤ 10⁶). That gap is exactly why we segment: base primes up to √R, window buffer of size R − L.
Q2.Is the range inclusive of both L and R?
Yes, [L, R] inclusive. Index x maps to slot x − L, so the buffer has R − L + 1 entries.
Q3.Can L be 1 (or 0)?
L can be 1. 1 is not prime, and no base prime ever crosses it out, so I clear its slot explicitly. If L were 0 I'd also clear slot 0 and 1.
Q4.Do you want the primes themselves or just the count?
Either — the sieve is identical. I collect the survivors for the list, or tally them for a count query.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You want primes in a high window [L, R] where R can be up to 10¹² but R−L is small. A plain sieve of size R won't fit in memory. The fix: sieve normally up to √R to get the 'base primes', then use only those base primes to cross out composites inside a boolean window of size R−L+1. Any composite x in [L, R] has a prime factor ≤ √x ≤ √R, so the base primes are enough to mark every composite in the window. Time is O((R−L) log log R + √R log log √R), memory is O(R−L + √R).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise that primes up to √R are sufficient to sieve any window ending at R, and whether you can map a number x to its slot x − L in a shifted boolean array without off-by-one errors.

Where candidates slip

Trying to allocate a boolean array of size R (out of memory for R ~ 10¹²), forgetting the x − L index shift, or mishandling L = 1 so that 1 is reported as prime.

How to stand out

State the invariant out loud — 'every composite ≤ R has a prime factor ≤ √R' — then derive that the base sieve only needs √R, and compute the first in-window multiple as ceil(L/p)·p instead of looping up from p.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sieve Everything Up To R (Baseline)	`O(R log log R)`	`O(R)`	Mention first to expose why the obvious idea fails — it anchors the memory problem the segmented sieve solves.	Read
2	Segmented Sieve (Optimal)Optimal	`O((R − L) log log R + √R log log √R)`	`O(R − L + √R)`	The answer they want for primes in a high window. Lead with 'a composite ≤ R has a prime factor ≤ √R, so I only sieve base primes up to √R'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewStage 1: plain sieve up to floor(sqrt(R))for each base prime pdoneExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sieve Everything Up To R (Baseline)

TimeO(R log log R)SpaceO(R)

Mention first to expose why the obvious idea fails — it anchors the memory problem the segmented sieve solves.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The most direct idea: run a normal Sieve of Eratosthenes up to R, then read off the primes that happen to fall in [L, R]. What goes wrong when R is 10¹²?

2Hint 2Explore hint

A boolean array of size R + 1 needs about R bytes. For R = 10¹² that's a terabyte — it simply will not allocate.

3Hint 3Explore hint

We don't actually need primality for every number up to R, only for the R − L numbers in the window. Can we restrict the work to that band?

A · Core idea

The literal reading of 'primes in [L, R]' is: sieve all primes up to R the usual way, then keep the ones that land in the window. Allocate isPrime[0..R], cross out multiples of each prime, and finally collect indices in [L, R].

Why it is correct. It is just the plain Sieve of Eratosthenes followed by a range filter. Correctness is inherited directly from the standard sieve: every composite ≤ R gets crossed out, every prime survives, and we report only those in [L, R].

Why it does not ship. The fatal flaw is space, not time. The boolean array has R + 1 entries. With R around 10¹² that is on the order of a terabyte of memory — the allocation fails before the algorithm even starts. Even when R is merely 10⁹, you are burning a gigabyte to discard all but a thin slice of it. We are computing primality for 10¹² numbers when the question only asked about the 10⁶ in the window.

The wasted-work insight. Almost all of the array — every index outside [L, R] — is computed and then thrown away. That mismatch between work done and answer needed is the signal to segment: bring the sieve to the window instead of bringing the window to a full sieve.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

L = 10, R = 20

sieve to 20

cross out multiples of 2,3 up to 20

Stateprimes ≤ 20 = {2,3,5,7,11,13,17,19}

Final result[11, 13, 17, 19] (but infeasible once R is large)

C · Code with teaching comments

Reference implementation previewpublic List<Long> primesInRange(long L, long R) { // Baseline: only works when R is small enough to allocate R+1 booleans. boolean[] composite = new boolean[(int) (R + 1)]; for (long p = 2; p * p <= R; p++) { if (!composite[(int) p]) {Explore the full code

solution.javaJava

Sieve Everything Up To R (Baseline) — reference

3 teaching notes

1
public List<Long> primesInRange(long L, long R) {
2
    // Baseline: only works when R is small enough to allocate R+1 booleans.
3
    // The fatal line: size scales with R, so it fails to allocate when R is ~10¹².
4
    boolean[] composite = new boolean[(int) (R + 1)];
5
    for (long p = 2; p * p <= R; p++) {
6
        if (!composite[(int) p]) {
7
            // p and m are long so p*p doesn't overflow, but the array index cast still
8
            // needs R to fit in an int.
9
            for (long m = p * p; m <= R; m += p) {
10
                composite[(int) m] = true;
11
            }
12
        }
13
    }
14
    List<Long> primes = new ArrayList<>();
15
    // Filter step keeps only [L, R] — most of the sieved array is discarded, which is
16
    // the wasted work.
17
    for (long x = Math.max(2, L); x <= R; x++) {
18
        if (!composite[(int) x]) primes.add(x);
19
    }
20
    return primes;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(R log log R) timeO(R) spaceOpen the invariant and proofExplore the proof

This baseline is correct and is the right tool when R is small (say ≤ 10⁷). It fails for large R purely on memory: you allocate O(R) but only O(R − L) of it matters. Recognising that mismatch is what motivates sieving only the window.

ComplexityO(R log log R) time, O(R) space — A full sieve up to R does O(R log log R) crossing-out work and allocates an O(R) boolean array. The time is fine asymptotically, but the O(R) space is the killer: for R near 10¹² the array cannot fit in memory.

E · Edge cases and pitfalls3Allocating an array of size R when R is large — out of memory.Explore edge cases

Pitfalls

Allocating an array of size R when R is large — out of memory.
Casting R to int for the array size — overflows when R exceeds 2³¹.
Believing it's 'fast enough' because the time bound looks fine — the blocker is space, not time.

03.2

Approach 2 of 2 · Optimal

Segmented Sieve (Optimal)

TimeO((R − L) log log R + √R log log √R)SpaceO(R − L + √R)

The answer they want for primes in a high window. Lead with 'a composite ≤ R has a prime factor ≤ √R, so I only sieve base primes up to √R'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every composite number x has a prime factor no bigger than √x. If x ≤ R, that factor is ≤ √R. What does that tell you about which primes you actually need to cross out composites in [L, R]?

2Hint 2Explore hint

Step 1: run an ordinary sieve up to √R to get the 'base primes'. Step 2: make a boolean window of size R − L + 1 where slot i represents the number L + i.

3Hint 3Explore hint

For each base prime p, find the first multiple of p that is ≥ L (use ceil(L / p) * p), but never start below p*p, then cross out that multiple, the next, and so on up to R — writing to slot m − L.

A · Core idea

Split the job into two stages. Stage 1 — base primes. Run a normal Sieve of Eratosthenes up to floor(√R) and collect those primes. Stage 2 — sieve the window. Allocate a boolean array mark of length R − L + 1, where slot i stands for the number L + i, and assume every number in the window is prime. For each base prime p, cross out its multiples that fall inside [L, R]. Whatever stays marked is prime.

Why base primes up to √R suffice. Take any composite x in [L, R]. Write x = a·b with a ≤ b; then a ≤ √x ≤ √R. The smallest prime factor of x is therefore at most √R, so it appears in our base list — and when that base prime sweeps the window it crosses x out. No composite can escape, because each has a witness ≤ √R. Primes larger than √R are never needed as erasers; they only ever appear as survivors.

Why the shift `x → x − L`. The window doesn't start at 0, so we can't index it by the number itself (that would need an array of size R). Instead slot i holds number L + i, i.e. number x lives at slot x − L. Every read and write goes through that offset. Dropping the − L is the classic bug — it silently writes out of bounds or to the wrong cell.

Why the start is `max(p*p, ceil(L/p)·p)`. We want the first multiple of p that is both inside the window (≥ L) and not smaller than p*p (multiples below p*p have a smaller prime factor that already handles them, exactly as in the plain sieve). The first multiple of p at or above L is ceil(L / p) · p, computed as ((L + p − 1) / p) · p with integer division — no scanning loop needed. Taking the max with p*p keeps the start from dipping below where this prime should begin.

Why `L == 1` needs a special line. The number 1 is not prime, but it has no prime factor, so no base prime ever crosses it out. If L == 1, slot 0 (which represents 1) survives by default and would wrongly be reported. Clear it explicitly. (If L == 0, clear slots for 0 and 1.)

Why it's overflow-safe. With R near 10¹², products like p*p and the multiple arithmetic exceed a 32-bit int. In Java everything in the multiple computation is long; in Python integers are unbounded so there is nothing to guard.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

L = 10, R = 20

Array state

init

all slots assumed prime (numbers 10..20)

L ↓

✓10

[0]

✓11

[1]

✓12

[2]

✓13

[3]

✓14

[4]

✓15

[5]

✓16

[6]

✓17

[7]

✓18

[8]

✓19

[9]

✓20

[10]

Current pointerResolved stateNot processed

Final result[11, 13, 17, 19]

C · Code with teaching comments

solution.javaJava

Segmented Sieve (Optimal) — optimal

5 teaching notes

1
public List<Long> primesInRange(long L, long R) {
2
    // Base primes only need to reach √R; the +1 guards floating-point rounding of the
3
    // square root.
4
    int limit = (int) Math.sqrt((double) R) + 1;
5
    // Stage 1: plain sieve up to sqrt(R) for the base primes.
6
    boolean[] isComposite = new boolean[limit + 1];
7
    List<Integer> basePrimes = new ArrayList<>();
8
    for (int p = 2; p <= limit; p++) {
9
        if (!isComposite[p]) {
10
            basePrimes.add(p);
11
            // Cast p to long before squaring so p*p can't overflow int even though
12
            // limit itself is small.
13
            for (long m = (long) p * p; m <= limit; m += p) {
14
                isComposite[(int) m] = true;
15
            }
16
        }
17
    }
18
    // Stage 2: sieve the window [L, R]; slot i represents number L + i.
19
    int size = (int) (R - L + 1);
20
    boolean[] mark = new boolean[size]; // false = still prime
21
    for (int p : basePrimes) {
22
        long pp = (long) p * p;
23
        // ceil(L/p)*p is the first multiple of p ≥ L; max with p*p mirrors the plain
24
        // sieve's start. All long → overflow-safe at R ~ 10¹².
25
        long firstMultiple = Math.max(pp, ((L + p - 1) / p) * (long) p);
26
        for (long m = firstMultiple; m <= R; m += p) {
27
            // The index shift: number m lives at slot m − L. Omitting − L is the
28
            // signature bug of this problem.
29
            mark[(int) (m - L)] = true;
30
        }
31
    }
32
    if (L == 1) mark[0] = true; // 1 is not prime, no base prime crosses it out
33
    List<Long> primes = new ArrayList<>();
34
    for (int i = 0; i < size; i++) {
35
        if (!mark[i]) primes.add(L + i);
36
    }
37
    return primes;
38
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.38 lines

D · Why it works and complexityO((R − L) log log R + √R log log √R) timeO(R − L + √R) spaceOpen the invariant and proofExplore the proof

The segmented sieve is the plain sieve with the eraser set trimmed to exactly what the window needs: primes up to √R. The two ideas that make it work are independent — 'only √R primes can witness a composite ≤ R' (correctness) and 'index by offset from L' (fitting the window in memory). Master the ceil(L/p)·p start and the L = 1 edge and the rest is mechanical.

ComplexityO((R − L) log log R + √R log log √R) time, O(R − L + √R) space — Stage 1 sieves up to √R in O(√R log log √R). Stage 2: each base prime p crosses out about (R − L)/p slots, and summing 1/p over primes ≤ √R gives a log log factor, so the window work is O((R − L) log log R). Space is the window O(R − L) plus the base sieve O(√R).

E · Edge cases and pitfalls8L = 1, R = 1 — Window has one slot for the number 1; the L == 1 line clears it → empty result.Explore edge cases

Edge cases handled

L = 1, R = 1Window has one slot for the number 1; the L == 1 line clears it → empty result.
L = R = 999999999989 (a prime)No base prime ≤ √R divides it, so its single slot survives → [999999999989].
L = 8, R = 10Base primes {2,3}: 8,9,10 all crossed out → empty list, correctly no primes in [8,10].

Pitfalls

Forgetting the x − L index shift — writes land in the wrong slot or out of bounds.
Sizing the base sieve to R instead of √R — that reintroduces the memory blowup.
Computing the first multiple by looping up from p instead of ceil(L/p)·p — slow when L is huge.
Not clearing slot 0 when L == 1 — reports 1 as prime.
Using int for p*p or multiple arithmetic in Java with R ~ 10¹² — overflow.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<Long> primesInRange(long L, long R) { int limit = (int) Math.sqrt((double) R) + 1; // Stage 1: plain sieve up to sqrt(R) for the base primes. boolean[] isComposite = new boolean[limit + 1]; List<Integer> basePrimes = new ArrayList<>();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public List<Long> primesInRange(long L, long R) {
    int limit = (int) Math.sqrt((double) R) + 1;
    // Stage 1: plain sieve up to sqrt(R) for the base primes.
    boolean[] isComposite = new boolean[limit + 1];
    List<Integer> basePrimes = new ArrayList<>();
    for (int p = 2; p <= limit; p++) {
        if (!isComposite[p]) {
            basePrimes.add(p);
            for (long m = (long) p * p; m <= limit; m += p) {
                isComposite[(int) m] = true;
            }
        }
    }
    // Stage 2: sieve the window [L, R]; slot i represents number L + i.
    int size = (int) (R - L + 1);
    boolean[] mark = new boolean[size]; // false = still prime
    for (int p : basePrimes) {
        long pp = (long) p * p;
        long firstMultiple = Math.max(pp, ((L + p - 1) / p) * (long) p);
        for (long m = firstMultiple; m <= R; m += p) {
            mark[(int) (m - L)] = true;
        }
    }
    if (L == 1) mark[0] = true; // 1 is not prime, no base prime crosses it out
    List<Long> primes = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        if (!mark[i]) primes.add(L + i);
    }
    return primes;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Indexing the window by the number instead of the offset

Slot i represents L + i, so number m must be written at m − L. Writing mark[m] indexes far outside the size-(R−L+1) array and throws (or corrupts memory in C-like languages).

Explore the code comparison

Don't write this

for (long m = firstMultiple; m <= R; m += p) {
    mark[(int) m] = true; // index up to R — out of bounds
}

Write this instead

for (long m = firstMultiple; m <= R; m += p) {
    mark[(int) (m - L)] = true; // shift number into window slot
}

Finding the first in-window multiple by scanning

Looping m from p upward until m ≥ L wastes ceil(L/p) iterations — catastrophic when L is ~10¹². Compute the first multiple in O(1) with ceil(L/p)·p.

Explore the code comparison

Don't write this

m = p
while m < L:        # up to 10^12 / p iterations
    m += p
start = max(p * p, m)

Write this instead

start = max(p * p, ((L + p - 1) // p) * p)  # O(1) ceil(L/p)*p

Letting 1 leak through when L = 1

1 has no prime factor, so no base prime ever crosses out its slot. Without an explicit clear, the survivor scan reports 1 as prime.

Explore the code comparison

Don't write this

mark = [False] * size
# ... cross out base-prime multiples ...
return [L + i for i in range(size) if not mark[i]]  # includes 1

Write this instead

mark = [False] * size
# ... cross out base-prime multiples ...
if L == 1:
    mark[0] = True
return [L + i for i in range(size) if not mark[i]]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sieve base primes up to √R, then cross out their multiples inside the window [L, R]

Code pattern to memorize

base = primesUpTo(floor(sqrt(R)))   # plain sieve
mark = [True] * (R - L + 1)            # index i ↔ number L+i
for p in base:
    start = max(p*p, ((L + p - 1) // p) * p)   # first multiple of p ≥ L, but ≥ p*p
    for m from start to R step p:
        mark[m - L] = False
if L == 1: mark[0] = False   # 1 is not prime
primes = [L + i for i, ok in enumerate(mark) if ok]

Rules to remember

1The base primes only need to reach √R, never R — that is the whole point and the reason the window fits in memory.
2Offset every window index by L: number x lives at mark[x − L]. Forgetting the − L shift is the signature bug of this problem.
3Start crossing out p's multiples at max(p*p, first multiple of p ≥ L) — and compute that first multiple as ceil(L / p) * p, not by scanning.
4Handle L == 1 explicitly: 1 is not prime but no base prime crosses it out, so it leaks into the result unless you clear mark[0].
5Use long for p*p and for the multiple arithmetic in Java — with R near 10¹² these products overflow a 32-bit int.

Use this pattern when

You need every prime in a **high range** [L, R] where R is far too large to sieve directly
The window width R − L is small (fits in memory) even though R itself is huge
You already need a √R base sieve and just want to extend it to a shifted window
Counting or listing primes in [L, R] for number-theory queries

Choose another pattern when

You need all primes from 2 up to a modest n → the plain Sieve of Eratosthenes is simpler
You only need to test **one** number for primality → trial division to √x or Miller–Rabin
The window R − L itself is enormous (also ~10¹²) → no boolean window fits; you need a different idea
R is small (≤ 10⁷) → just sieve directly, no segmentation needed

Interview takeaway

The segmented sieve is the plain sieve with one realisation: a composite in [L, R] is betrayed by a prime factor no larger than √R, so you never need primes beyond √R to clean the window. Precompute those base primes once, slide them across a size-(R−L) boolean buffer, and you sieve ranges that would never fit if addressed from 0. The index shift `x → x − L` and the `L == 1` special case are the two details that decide whether your code is correct.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSegmented Sieve over a high window. Reach for it whenever you need primes (or a multiplicative property) in [L, R] with R too large to sieve directly but R − L small. The recipe — base primes up to √R, then offset crossing-out — generalises to segmented totient and segmented smallest-prime-factor tables.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sieve of Eratosthenes
The base-prime stage IS a plain sieve; segmenting just extends it to a shifted window.
Count Primes
Coming soon
Count survivors instead of collecting them — same sieve, tally the window.
Smallest Prime Factor Sieve
Coming soon
Store smallest prime factors over a range to factorise any x in the window quickly.
Euler's Totient Function
Segment the totient sieve the same way to compute φ over a high range.

Same pattern

←

Nth Fibonacci Number

Continue · Next problem

Sum of Digits (Digital Root)

mediumMath GeometrySometimes asked

Segmented Sieve

Math & Number Theory · 29 of 36 · 11 min

Given two integers L and R (with L ≤ R), return all prime numbers in the inclusive range [L, R] in increasing order.

In plain English

Examples

Example 1

Input: L = 10, R = 20
Output: [11, 13, 17, 19]
Note: Base primes up to √20 ≈ 4 are {2, 3}. They cross out 10,12,14,16,18,20 (multiples of 2) and 12,15,18 (multiples of 3) inside the window; 11,13,17,19 survive.

Example 2

Input: L = 1, R = 10
Output: [2, 3, 5, 7]
Note: Same as a normal sieve over [1,10]; slot for 1 is cleared explicitly because no prime crosses it out.

Example 3

Input: L = 100, R = 110
Output: [101, 103, 107, 109]
Note: Base primes up to √110 ≈ 10 are {2,3,5,7}. After crossing out their multiples in [100,110], four primes remain.

Constraints

1 ≤ L ≤ R ≤ 10¹² (R is huge; R − L is the part that fits in memory)
0 ≤ R − L ≤ 10⁶ (window width — the boolean buffer is O(R − L))
Return primes in ascending order
L may equal 1 → 1 is not prime and must be excluded

Clarifying questions4First question: How large can R get, and how wide is the window R − L?Explore questions

Q1.How large can R get, and how wide is the window R − L?
R can be ~10¹² (too big to sieve directly), but R − L fits in memory (≤ 10⁶). That gap is exactly why we segment: base primes up to √R, window buffer of size R − L.
Q2.Is the range inclusive of both L and R?
Yes, [L, R] inclusive. Index x maps to slot x − L, so the buffer has R − L + 1 entries.
Q3.Can L be 1 (or 0)?
L can be 1. 1 is not prime, and no base prime ever crosses it out, so I clear its slot explicitly. If L were 0 I'd also clear slot 0 and 1.
Q4.Do you want the primes themselves or just the count?
Either — the sieve is identical. I collect the survivors for the list, or tally them for a count query.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise that primes up to √R are sufficient to sieve any window ending at R, and whether you can map a number x to its slot x − L in a shifted boolean array without off-by-one errors.

Where candidates slip

Trying to allocate a boolean array of size R (out of memory for R ~ 10¹²), forgetting the x − L index shift, or mishandling L = 1 so that 1 is reported as prime.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sieve Everything Up To R (Baseline)	`O(R log log R)`	`O(R)`	Mention first to expose why the obvious idea fails — it anchors the memory problem the segmented sieve solves.	Read
2	Segmented Sieve (Optimal)Optimal	`O((R − L) log log R + √R log log √R)`	`O(R − L + √R)`	The answer they want for primes in a high window. Lead with 'a composite ≤ R has a prime factor ≤ √R, so I only sieve base primes up to √R'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sieve Everything Up To R (Baseline)

TimeO(R log log R)SpaceO(R)

Mention first to expose why the obvious idea fails — it anchors the memory problem the segmented sieve solves.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The most direct idea: run a normal Sieve of Eratosthenes up to R, then read off the primes that happen to fall in [L, R]. What goes wrong when R is 10¹²?

2Hint 2Explore hint

A boolean array of size R + 1 needs about R bytes. For R = 10¹² that's a terabyte — it simply will not allocate.

3Hint 3Explore hint

We don't actually need primality for every number up to R, only for the R − L numbers in the window. Can we restrict the work to that band?

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

L = 10, R = 20

sieve to 20

cross out multiples of 2,3 up to 20

Stateprimes ≤ 20 = {2,3,5,7,11,13,17,19}

Final result[11, 13, 17, 19] (but infeasible once R is large)

C · Code with teaching comments

solution.javaJava

Sieve Everything Up To R (Baseline) — reference

3 teaching notes

1
public List<Long> primesInRange(long L, long R) {
2
    // Baseline: only works when R is small enough to allocate R+1 booleans.
3
    // The fatal line: size scales with R, so it fails to allocate when R is ~10¹².
4
    boolean[] composite = new boolean[(int) (R + 1)];
5
    for (long p = 2; p * p <= R; p++) {
6
        if (!composite[(int) p]) {
7
            // p and m are long so p*p doesn't overflow, but the array index cast still
8
            // needs R to fit in an int.
9
            for (long m = p * p; m <= R; m += p) {
10
                composite[(int) m] = true;
11
            }
12
        }
13
    }
14
    List<Long> primes = new ArrayList<>();
15
    // Filter step keeps only [L, R] — most of the sieved array is discarded, which is
16
    // the wasted work.
17
    for (long x = Math.max(2, L); x <= R; x++) {
18
        if (!composite[(int) x]) primes.add(x);
19
    }
20
    return primes;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(R log log R) timeO(R) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Allocating an array of size R when R is large — out of memory.Explore edge cases

Pitfalls

Allocating an array of size R when R is large — out of memory.
Casting R to int for the array size — overflows when R exceeds 2³¹.
Believing it's 'fast enough' because the time bound looks fine — the blocker is space, not time.

03.2

Approach 2 of 2 · Optimal

Segmented Sieve (Optimal)

TimeO((R − L) log log R + √R log log √R)SpaceO(R − L + √R)

The answer they want for primes in a high window. Lead with 'a composite ≤ R has a prime factor ≤ √R, so I only sieve base primes up to √R'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every composite number x has a prime factor no bigger than √x. If x ≤ R, that factor is ≤ √R. What does that tell you about which primes you actually need to cross out composites in [L, R]?

2Hint 2Explore hint

Step 1: run an ordinary sieve up to √R to get the 'base primes'. Step 2: make a boolean window of size R − L + 1 where slot i represents the number L + i.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

L = 10, R = 20

Array state

init

all slots assumed prime (numbers 10..20)

L ↓

✓10

[0]

✓11

[1]

✓12

[2]

✓13

[3]

✓14

[4]

✓15

[5]

✓16

[6]

✓17

[7]

✓18

[8]

✓19

[9]

✓20

[10]

Current pointerResolved stateNot processed

Final result[11, 13, 17, 19]

C · Code with teaching comments

solution.javaJava

Segmented Sieve (Optimal) — optimal

5 teaching notes

1
public List<Long> primesInRange(long L, long R) {
2
    // Base primes only need to reach √R; the +1 guards floating-point rounding of the
3
    // square root.
4
    int limit = (int) Math.sqrt((double) R) + 1;
5
    // Stage 1: plain sieve up to sqrt(R) for the base primes.
6
    boolean[] isComposite = new boolean[limit + 1];
7
    List<Integer> basePrimes = new ArrayList<>();
8
    for (int p = 2; p <= limit; p++) {
9
        if (!isComposite[p]) {
10
            basePrimes.add(p);
11
            // Cast p to long before squaring so p*p can't overflow int even though
12
            // limit itself is small.
13
            for (long m = (long) p * p; m <= limit; m += p) {
14
                isComposite[(int) m] = true;
15
            }
16
        }
17
    }
18
    // Stage 2: sieve the window [L, R]; slot i represents number L + i.
19
    int size = (int) (R - L + 1);
20
    boolean[] mark = new boolean[size]; // false = still prime
21
    for (int p : basePrimes) {
22
        long pp = (long) p * p;
23
        // ceil(L/p)*p is the first multiple of p ≥ L; max with p*p mirrors the plain
24
        // sieve's start. All long → overflow-safe at R ~ 10¹².
25
        long firstMultiple = Math.max(pp, ((L + p - 1) / p) * (long) p);
26
        for (long m = firstMultiple; m <= R; m += p) {
27
            // The index shift: number m lives at slot m − L. Omitting − L is the
28
            // signature bug of this problem.
29
            mark[(int) (m - L)] = true;
30
        }
31
    }
32
    if (L == 1) mark[0] = true; // 1 is not prime, no base prime crosses it out
33
    List<Long> primes = new ArrayList<>();
34
    for (int i = 0; i < size; i++) {
35
        if (!mark[i]) primes.add(L + i);
36
    }
37
    return primes;
38
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.38 lines

D · Why it works and complexityO((R − L) log log R + √R log log √R) timeO(R − L + √R) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8L = 1, R = 1 — Window has one slot for the number 1; the L == 1 line clears it → empty result.Explore edge cases

Edge cases handled

L = 1, R = 1Window has one slot for the number 1; the L == 1 line clears it → empty result.
L = R = 999999999989 (a prime)No base prime ≤ √R divides it, so its single slot survives → [999999999989].
L = 8, R = 10Base primes {2,3}: 8,9,10 all crossed out → empty list, correctly no primes in [8,10].

Pitfalls

Forgetting the x − L index shift — writes land in the wrong slot or out of bounds.
Sizing the base sieve to R instead of √R — that reintroduces the memory blowup.
Computing the first multiple by looping up from p instead of ceil(L/p)·p — slow when L is huge.
Not clearing slot 0 when L == 1 — reports 1 as prime.
Using int for p*p or multiple arithmetic in Java with R ~ 10¹² — overflow.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Indexing the window by the number instead of the offset

Slot i represents L + i, so number m must be written at m − L. Writing mark[m] indexes far outside the size-(R−L+1) array and throws (or corrupts memory in C-like languages).

Explore the code comparison

Don't write this

for (long m = firstMultiple; m <= R; m += p) {
    mark[(int) m] = true; // index up to R — out of bounds
}

Write this instead

for (long m = firstMultiple; m <= R; m += p) {
    mark[(int) (m - L)] = true; // shift number into window slot
}

Finding the first in-window multiple by scanning

Looping m from p upward until m ≥ L wastes ceil(L/p) iterations — catastrophic when L is ~10¹². Compute the first multiple in O(1) with ceil(L/p)·p.

Explore the code comparison

Don't write this

m = p
while m < L:        # up to 10^12 / p iterations
    m += p
start = max(p * p, m)

Write this instead

start = max(p * p, ((L + p - 1) // p) * p)  # O(1) ceil(L/p)*p

Letting 1 leak through when L = 1

1 has no prime factor, so no base prime ever crosses out its slot. Without an explicit clear, the survivor scan reports 1 as prime.

Explore the code comparison

Don't write this

mark = [False] * size
# ... cross out base-prime multiples ...
return [L + i for i in range(size) if not mark[i]]  # includes 1

Write this instead

mark = [False] * size
# ... cross out base-prime multiples ...
if L == 1:
    mark[0] = True
return [L + i for i in range(size) if not mark[i]]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sieve base primes up to √R, then cross out their multiples inside the window [L, R]

Code pattern to memorize

base = primesUpTo(floor(sqrt(R)))   # plain sieve
mark = [True] * (R - L + 1)            # index i ↔ number L+i
for p in base:
    start = max(p*p, ((L + p - 1) // p) * p)   # first multiple of p ≥ L, but ≥ p*p
    for m from start to R step p:
        mark[m - L] = False
if L == 1: mark[0] = False   # 1 is not prime
primes = [L + i for i, ok in enumerate(mark) if ok]

Rules to remember

1The base primes only need to reach √R, never R — that is the whole point and the reason the window fits in memory.
2Offset every window index by L: number x lives at mark[x − L]. Forgetting the − L shift is the signature bug of this problem.
3Start crossing out p's multiples at max(p*p, first multiple of p ≥ L) — and compute that first multiple as ceil(L / p) * p, not by scanning.
4Handle L == 1 explicitly: 1 is not prime but no base prime crosses it out, so it leaks into the result unless you clear mark[0].
5Use long for p*p and for the multiple arithmetic in Java — with R near 10¹² these products overflow a 32-bit int.

Use this pattern when

You need every prime in a **high range** [L, R] where R is far too large to sieve directly
The window width R − L is small (fits in memory) even though R itself is huge
You already need a √R base sieve and just want to extend it to a shifted window
Counting or listing primes in [L, R] for number-theory queries

Choose another pattern when

You need all primes from 2 up to a modest n → the plain Sieve of Eratosthenes is simpler
You only need to test **one** number for primality → trial division to √x or Miller–Rabin
The window R − L itself is enormous (also ~10¹²) → no boolean window fits; you need a different idea
R is small (≤ 10⁷) → just sieve directly, no segmentation needed

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sieve of Eratosthenes
The base-prime stage IS a plain sieve; segmenting just extends it to a shifted window.
Count Primes
Coming soon
Count survivors instead of collecting them — same sieve, tally the window.
Smallest Prime Factor Sieve
Coming soon
Store smallest prime factors over a range to factorise any x in the window quickly.
Euler's Totient Function
Segment the totient sieve the same way to compute φ over a high range.

Same pattern

←

Nth Fibonacci Number

Continue · Next problem

Sum of Digits (Digital Root)