Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
To list every prime up to n, don't test each number for primality — instead cross out multiples. Keep a boolean array `isPrime[0..n]`, and for each prime p starting at 2, mark p's multiples as composite. The two tricks that make it fast: only loop p while p*p ≤ n, and start crossing out from p*p (not 2*p), because every smaller multiple of p was already crossed out by a smaller prime. Total work is O(n log log n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know the sieve and can justify its two non-obvious optimisations — starting the inner loop at p*p and stopping the outer loop at √n — rather than reciting the loop bounds from memory.
Where candidates slip
Starting the inner loop at 2*p (correct but slower), running the outer loop all the way to n (wasted passes), or forgetting to mark 0 and 1 as non-prime.
How to stand out
Explain WHY p*p is the right start (smaller multiples already crossed out by smaller primes) and state the O(n log log n) bound, mentioning it comes from the sum of 1/p over primes ≤ n.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewisPrime[0..n] = true isPrime[0]=isPrime[1]=falsep*p <= n ?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Trial Division Per Number (Baseline)
1Hint 1Explore hintHide hint
The dictionary definition of prime gives a direct test: a number x is prime if nothing in [2, x−1] divides it. How would you turn that into code for every number up to n?
2Hint 2Explore hintHide hint
You don't need to test divisors up to x−1 — if x = a*b then one of a, b is ≤ √x, so testing divisors up to √x suffices.
3Hint 3Explore hintHide hint
Wrap that √x primality test in a loop over every x from 2 to n. That's n tests, each up to √n work.
A · Core idea
The most literal reading of 'find all primes' is: for each number from 2 to n, run a primality test and keep it if it passes. The standard test asks whether any integer in [2, √x] divides x — if none does, x is prime.
Why √x is enough for one test. If x is composite, it factors as x = a·b with a ≤ b. Then a·a ≤ a·b = x, so a ≤ √x. Every composite therefore has a divisor at or below √x, so finding none up to √x proves x is prime. This already beats the naive 'test up to x−1' check.
Why this still loses to the sieve. We pay the √x test once per number, with no sharing of work between numbers. The number 90 gets tested for divisibility by 2, then 91 gets tested from scratch, then 92, and so on — even though 'is it even?' was answered a moment ago. The total climbs to roughly n·√n. For n = 10⁶ that's on the order of 10⁹ operations, noticeably slower than the sieve's ~10⁷.
When it's actually the right call. If you only need to test one number — 'is 1000003 prime?' — there's nothing to amortise and trial division to √x is the simplest correct answer. The sieve only wins when you want all primes up to n, so the crossing-out work is shared across the whole range.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 10x=2
no divisor in [2, √2]
prime[2, 3, 5, 7]C · Code with teaching comments
Reference implementation previewpublic List<Integer> primesUpTo(int n) { List<Integer> primes = new ArrayList<>(); for (int x = 2; x <= n; x++) { if (isPrime(x)) { primes.add(x);Explore the full codeHide the full code
D · Why it works and complexityO(n √n) timeO(1) extra spaceOpen the invariant and proofExplore the proofHide the proof
Trial division is correct and is the right tool for a single primality query. It loses for 'all primes up to n' purely because it shares no work between numbers — each test starts from zero. The sieve's whole advantage is that one prime's crossing-out pass benefits the entire range at once.
ComplexityO(n √n) time, O(1) extra space — For each of the n numbers we try divisors up to √x ≤ √n, so the total is about n·√n. No array needed beyond the output, hence O(1) extra space.
E · Edge cases and pitfalls3Testing divisors up to x−1 instead of √x — correct but quadratic per number.Explore edge casesHide edge cases
Pitfalls
- Testing divisors up to x−1 instead of √x — correct but quadratic per number.
- Reusing this for 'all primes up to n' when n is large — the sieve is dramatically faster.
- Forgetting the x < 2 guard, which would call 0 and 1 prime.
Approach 2 of 2 · Optimal
Sieve of Eratosthenes (Optimal)
1Hint 1Explore hintHide hint
Instead of asking 'is x prime?' for every x, flip it: assume everything is prime, then let each prime delete the numbers it divides. What's left undeleted must be prime.
2Hint 2Explore hintHide hint
Walk p from 2 upward. When you reach a p that's still marked prime, cross out p's multiples. Why can you stop increasing p once p*p > n?
3Hint 3Explore hintHide hint
When crossing out p's multiples, you can start at p*p instead of 2*p — every multiple of p smaller than p*p has a smaller prime factor and was already crossed out.
A · Core idea
Allocate isPrime[0..n], set everything true, then mark 0 and 1 false. Sweep p from 2 upward. Whenever isPrime[p] is still true, p is genuinely prime — so cross out all of its multiples as composite. At the end, every index still marked true is prime.
Why p must be prime when we reach it. We process p in increasing order. If p had a smaller prime factor q < p, then when we processed q we already crossed out all multiples of q — including p itself. So the only way isPrime[p] is still true when we arrive is that p has no smaller prime factor, i.e. p is prime. That is the correctness backbone: the sieve never crosses out a prime, and it crosses out every composite (since every composite has at least one prime factor ≤ its square root that will reach it).
Why crossing-out starts at p*p, not 2*p. Consider the multiples of p: 2p, 3p, 4p, …, up to (p−1)p, p·p, …. Every multiple kp with k < p has a factor k that is smaller than p, and that smaller factor's smallest prime divisor is itself ≤ k < p — meaning kp was already crossed out during an earlier prime's pass. The first multiple of p that no smaller prime has touched is p·p. Starting there skips a pile of redundant writes and is a pure optimisation, not a correctness requirement.
Why the outer loop stops at √n. If p > √n, then p·p > n, so there is no multiple of p in range left to cross out — the inner loop body would never execute. Any index above √n that is still marked true at that point is simply prime and needs no further work. Stopping the outer loop at p·p ≤ n avoids pointless iterations.
Why the time is O(n log log n). Prime p crosses out roughly n/p numbers. The total writes are n/2 + n/3 + n/5 + n/7 + … over primes ≤ n, which is n times the sum of reciprocals of primes. That prime-reciprocal sum grows like log log n — astonishingly slowly — so the whole sieve is near-linear. This is why the sieve crushes the O(n √n) trial-division approach.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 30Array state
init
all true except 0,1
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]C · Code with teaching comments
D · Why it works and complexityO(n log log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The sieve's speed comes from sharing work: one pass for prime p benefits the entire range, and the start-at-p*p trick means each composite is crossed out only by its prime factors that haven't appeared yet. The deep fact behind O(n log log n) is that primes thin out fast enough that Σ(1/p) barely grows — the harmonic-like sum over primes is log log n, not log n.
ComplexityO(n log log n) time, O(n) space — Each prime p does about n/p crossing-out steps. Summing n/p over all primes p ≤ n gives n · Σ(1/p), and Σ(1/p) over primes ≤ n grows like log log n (Mertens' theorem). So the total is O(n log log n). The boolean array is O(n) space.
E · Edge cases and pitfalls7n = 0 — n < 2 guard returns an empty list immediately.Explore edge casesHide edge cases
Edge cases handled
n = 0n < 2 guard returns an empty list immediately.n = 1n < 2 guard returns []; isPrime[1] would be false anyway.n = 2Outer loop condition 2*2=4 > 2 is false at once, so nothing is crossed out; 2 survives → [2].
Pitfalls
- Starting the inner loop at 2*p — still correct but does redundant writes; p*p is the right start.
- Running the outer loop to n instead of √n — wasted passes that cross out nothing new.
- Forgetting isPrime[0] and isPrime[1] = false — 0 and 1 wrongly reported as prime.
- Using int for p*p in Java when n is large — p*p overflows; use long or guard the multiplication.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<Integer> primesUpTo(int n) { List<Integer> primes = new ArrayList<>(); if (n < 2) return primes; boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Crossing out from 2*p instead of p*p
Every multiple of p below p*p (namely 2p, 3p, …, (p−1)p) has a factor smaller than p, so it was already crossed out by a smaller prime. Starting at 2*p repeats all that work — correct, just slower.
Explore the code comparisonHide the code comparison
Crossing out from 2*p instead of p*p
Every multiple of p below p*p (namely 2p, 3p, …, (p−1)p) has a factor smaller than p, so it was already crossed out by a smaller prime. Starting at 2*p repeats all that work — correct, just slower.
Don't write this
for (long m = 2 * p; m <= n; m += p) {
isPrime[(int) m] = false;
}Write this instead
for (long m = p * p; m <= n; m += p) {
isPrime[(int) m] = false;
}2Running the outer loop to n
Once p > √n, p*p > n and there is no multiple of p left in range — the inner loop never executes, so iterating p up to n is pure waste.
Explore the code comparisonHide the code comparison
Running the outer loop to n
Once p > √n, p*p > n and there is no multiple of p left in range — the inner loop never executes, so iterating p up to n is pure waste.
Don't write this
for (long p = 2; p <= n; p++) {
if (isPrime[(int) p]) {
for (long m = p * p; m <= n; m += p) isPrime[(int) m] = false;
}
}Write this instead
for (long p = 2; p * p <= n; p++) {
if (isPrime[(int) p]) {
for (long m = p * p; m <= n; m += p) isPrime[(int) m] = false;
}
}3Forgetting 0 and 1 are not prime
An all-true initial array leaves indices 0 and 1 marked prime; they are never crossed out, so they wrongly appear in the result.
Explore the code comparisonHide the code comparison
Forgetting 0 and 1 are not prime
An all-true initial array leaves indices 0 and 1 marked prime; they are never crossed out, so they wrongly appear in the result.
Don't write this
is_prime = [True] * (n + 1)
# 0 and 1 left as TrueWrite this instead
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseRevise
Carry the pattern into the interview
Pattern to remember
Cross out multiples instead of testing primality
Code pattern to memorize
isPrime[0..n] = true; isPrime[0] = isPrime[1] = false
for p from 2 while p*p <= n:
if isPrime[p]:
for m from p*p to n step p:
isPrime[m] = false
primes = all i with isPrime[i]Rules to remember
- 1Start the inner crossing-out at p*p, not 2p — every multiple of p below pp already got crossed out by a smaller prime factor.
- 2Stop the outer loop once p*p > n. Beyond that, any remaining unmarked number is prime; there is nothing left to cross out.
- 3Initialise
isPrime[0] = isPrime[1] = false— 0 and 1 are not prime, and forgetting this is the most common bug. - 4Use
p*pas along(or guard the loop) when n is large, sop*pdoesn't overflow a 32-bit int. - 5It's O(n log log n) time and O(n) space — near-linear, far better than testing each of n numbers in O(√n).
Use this pattern when
- You need **all** primes up to a fixed bound n, not just one primality test
- You'll do many primality queries over a fixed range → precompute once, answer in O(1)
- You need smallest-prime-factor or a multiplicative function (totient, Möbius) over a range
- n is up to ~10⁷–10⁸ and fits in memory as a boolean array
Choose another pattern when
- You only need to test **one** number for primality → trial division to √n is simpler
- The number is huge (hundreds of digits) → use Miller–Rabin, not a sieve
- The range bound n is astronomically large → segmented sieve or a different approach
- You need primes in a high window [L, R] with large L → segmented sieve, not the plain one
Interview takeaway
The sieve flips primality on its head: instead of asking 'is this number prime?' n times, it declares every number prime and lets each prime erase its own multiples. Starting at p*p and stopping at √n are the two optimisations that turn a naive O(n √n) idea into the near-linear O(n log log n) workhorse behind totient sieves, smallest-prime-factor tables, and fast factorisation.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Sieve over a range. Reach for it whenever you need a multiplicative or primality property for ALL values up to n, not a single query. The same cross-out skeleton powers the totient sieve, the Möbius sieve, and smallest-prime-factor tables.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Count PrimesComing soonSame sieve — count the survivors below n instead of collecting them.
- Segmented SieveFind primes in [L, R] with R up to 10¹² by sieving with base primes ≤ √R over a sliding window.
- Smallest Prime Factor SieveComing soonStore the smallest prime factor of each number to factorise any x ≤ n in O(log x).
- Euler's Totient FunctionA sieve variant computes φ for every value up to n in O(n log log n).