Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
For each query integer, decide 'Prime' or 'Not prime'. The point of the problem is the complexity: test divisibility only up to √n, not n. A number n > 1 is prime iff no integer in [2, √n] divides it — because any factor larger than √n is paired with one smaller than √n. Handle n < 2 as not prime, treat 2 (and 3) as prime, reject even numbers, then trial-divide by odd numbers 3, 5, 7, … while `i·i ≤ n`. Each query is O(√n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know that checking divisors only up to √n suffices (and why), and that you write the bound as `i*i <= n` to avoid sqrt rounding — the problem is named after its complexity for a reason.
Where candidates slip
Looping i up to n (O(n) instead of O(√n)), classifying 1 as prime, or using floating-point `i <= Math.sqrt(n)` and hitting rounding errors near perfect squares.
How to stand out
Explain the factor-pairing argument (a divisor > √n forces a co-divisor < √n), skip even divisors after 2 to halve the work, and mention switching to a sieve when many queries share a bounded range.
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 previewIs n prime?Many queries over a fixed range [1,N]?YesNoExplore 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
Brute Force — Trial Division up to n−1
1Hint 1Explore hintHide hint
By definition, n is prime if no integer from 2 to n−1 divides it.
2Hint 2Explore hintHide hint
Loop i from 2 to n−1; if any i divides n evenly, n is composite.
3Hint 3Explore hintHide hint
If the loop finishes with no divisor, n is prime. This is correct but O(n) — too slow for n up to 2×10⁹.
A · Core idea
The literal definition: a prime has no divisors strictly between 1 and itself, so test them all.
The loop. For each i from 2 to n − 1, check n % i == 0. The first such i proves n composite; reaching the end proves it prime. Guard n < 2 as not prime up front.
Why it's correct but unacceptable here. For a prime n = 2×10⁹ this performs ~2 billion modulo operations per query — far too slow within typical limits, and the problem name Time Complexity: Primality is a direct hint that O(n) is the wrong answer. We show it only to motivate the √n cutoff: most of those iterations are wasted because divisors past √n are redundant.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 12How to read it:Divisors pair across √n; anything found above it was already findable below.
Not primeC · Code with teaching comments
Reference implementation previewpublic boolean isPrime(long n) { if (n < 2) return false; for (long i = 2; i < n; i++) { // up to n-1 — O(n) if (n % i == 0) return false; }Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Every iteration past √n only finds the larger half of a factor pair you'd already have caught below √n — so half the search space is pure redundancy. That observation is exactly what the optimal version removes.
ComplexityO(n) time, O(1) space — The loop runs up to n−2 iterations in the worst case (a prime), each an O(1) modulo, giving O(n) time and O(1) space.
E · Edge cases and pitfalls3Running to n−1 — O(n) is too slow for n up to 2×10⁹.Explore edge casesHide edge cases
Pitfalls
- Running to n−1 — O(n) is too slow for n up to 2×10⁹.
- Treating 1 as prime by omitting the n < 2 guard.
- Starting the loop at 1 — 1 divides everything, falsely marking all numbers composite.
Approach 2 of 2 · Optimal
Trial Division up to √n, Skipping Evens (Optimal)
1Hint 1Explore hintHide hint
If n = a·b with a ≤ b then a ≤ √n, so any composite has a divisor at or below √n. Testing [2, √n] is sufficient.
2Hint 2Explore hintHide hint
Write the loop bound as `i*i <= n` rather than `i <= sqrt(n)` to avoid floating-point rounding near perfect squares.
3Hint 3Explore hintHide hint
Handle n < 2 (not prime), 2 and 3 (prime), and even n (not prime) first; then test only odd i = 3, 5, 7, … incrementing by 2.
A · Core idea
Cut the search at √n and skip the evens.
The √n cutoff. Suppose n is composite, n = a·b with a ≤ b. Then a·a ≤ a·b = n, so a ≤ √n. Every composite therefore has a divisor at or below √n. Contrapositive: if nothing in [2, √n] divides n, then n has no nontrivial divisor at all and is prime. That single fact turns the O(n) scan into O(√n).
Integer bound, not floating-point. Write the condition as i*i <= n. Using i <= Math.sqrt(n) invites trouble: sqrt returns a double that can be marginally below the true root for a perfect square (e.g. sqrt(n) computed as …9999), causing the loop to stop one short and misclassify n. The integer product comparison is exact.
Skip evens. After confirming n isn't even (and handling 2 itself as prime), no even number can be a factor, so we only need odd candidates: start i = 3 and step by 2. This halves the iterations.
Small-number guards. n < 2 → not prime. n < 4 (i.e. 2 or 3) → prime, which also lets the odd loop start cleanly at 3 without a special first iteration. n % 2 == 0 (and n ≥ 4) → not prime.
Per-query cost. Each query is O(√n) ≈ 45,000 modulo operations for n = 2×10⁹ — trivially fast, and well within limits for up to 30 queries.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 29Interactive diagram
Decision flow
guardsGuards short-circuit small and even cases; the loop only tests odd i up to √n.
PrimeC · Code with teaching comments
D · Why it works and complexityO(√n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Factor pairing (d, n/d) reflecting across √n is the whole idea: search only the smaller half. Combined with the i*i <= n integer test (no floating-point) and the odd-only step, it's the clean, bug-free primality check interviewers expect.
ComplexityO(√n) time, O(1) space — The loop runs while `i*i <= n` over odd i, i.e. about √n / 2 iterations, each an O(1) modulo → O(√n) time, O(1) space. The even-skip halves the constant.
E · Edge cases and pitfalls6n = 2 — n < 4 → returns true. The smallest and only even prime.Explore edge casesHide edge cases
Edge cases handled
n = 2n < 4 → returns true. The smallest and only even prime.n = 1n < 2 → returns false. 1 is not prime.n = 9Odd, i=3: 3·3=9 ≤ 9 and 9 % 3 == 0 → Not prime. The perfect square that `i*i <= n` catches exactly where floating-point might fail.
Pitfalls
- Using `i <= Math.sqrt(n)` — floating-point rounding can misclassify perfect squares like 9, 25, 49.
- Forgetting to special-case 2 while skipping evens — would wrongly mark 2 as composite or start the loop wrong.
- Off-by-one with `i < i*i` style conditions — use `i*i <= n` so the divisor equal to √n is tested.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean isPrime(long n) { if (n < 2) return false; if (n < 4) return true; // 2 and 3 are prime if (n % 2 == 0) return false; // drop all evens > 2 for (long i = 3; i * i <= n; i += 2) {// odd divisors up to sqrt(n)Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Scanning to n instead of √n
The factor-pairing argument shows divisors above √n are redundant. Looping to n is O(n) and times out for n up to 2×10⁹.
Explore the code comparisonHide the code comparison
Scanning to n instead of √n
The factor-pairing argument shows divisors above √n are redundant. Looping to n is O(n) and times out for n up to 2×10⁹.
Don't write this
for i in range(2, n): # O(n)
if n % i == 0:
return FalseWrite this instead
i = 3
while i * i <= n: # O(sqrt n)
if n % i == 0:
return False
i += 22Floating-point sqrt bound
Math.sqrt returns a double that may be slightly below the true root for perfect squares, stopping the loop one short and misclassifying n.
Explore the code comparisonHide the code comparison
Floating-point sqrt bound
Math.sqrt returns a double that may be slightly below the true root for perfect squares, stopping the loop one short and misclassifying n.
Don't write this
for (long i = 3; i <= Math.sqrt(n); i += 2) { ... } // rounding riskWrite this instead
for (long i = 3; i * i <= n; i += 2) { ... } // exact integer test3Treating 1 as prime
1 has no second distinct divisor, so it is not prime. Without the `n < 2` guard it slips through the loop (which never executes) and is wrongly reported prime.
Explore the code comparisonHide the code comparison
Treating 1 as prime
1 has no second distinct divisor, so it is not prime. Without the `n < 2` guard it slips through the loop (which never executes) and is wrongly reported prime.
Don't write this
def is_prime(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0: return False
return True # is_prime(1) → True (wrong)Write this instead
def is_prime(n):
if n < 2: return False
# ... restRevise
Carry the pattern into the interview
Pattern to remember
Trial division up to √n (factors come in pairs straddling √n)
Code pattern to memorize
def is_prime(n):
if n < 2: return False
if n < 4: return True # 2, 3
if n % 2 == 0: return False
i = 3
while i * i <= n: # only up to sqrt(n)
if n % i == 0: return False
i += 2 # skip evens
return TrueRules to remember
- 1Loop while `i * i <= n` (equivalently
i <= sqrt(n)) — never up to n. That's the whole O(√n) point. - 2Use
i * i <= nrather thani <= sqrt(n)to avoid floating-point rounding errors. - 3Handle small cases first:
n < 2→ not prime;2and3are prime. - 4After ruling out 2, only test odd divisors (
i += 2) — even factors are already covered. - 5
1is not prime, and neither are0or negatives.
Use this pattern when
- Deciding primality of one or a few moderate numbers (up to ~10¹²)
- When you need the answer per query, not all primes in a range
- Demonstrating the √n factor-pairing insight in an interview
- Numbers too large to sieve but small enough for trial division
Choose another pattern when
- Many primality tests over a fixed range [1, N] → precompute with a Sieve of Eratosthenes (O(N log log N))
- Numbers beyond ~10¹⁸ → need Miller–Rabin probabilistic / deterministic test
- You need the factorization, not just prime-or-not → factorize up to √n instead
- Counting primes ≤ N → prime-counting / sieve, not per-number trial division
Interview takeaway
Primality by trial division is O(√n) because divisors pair up across √n — find none below √n and there are none at all. The interview signal is choosing √n over n and writing `i*i <= n` to dodge floating-point; for many queries on a bounded range, switch to a sieve.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternTrial-division primality is O(√n) because a composite's factors pair across √n — test only the smaller half. Write the bound as `i*i <= n` to stay in integer arithmetic, and skip evens to halve the constant. For many queries over a fixed range, precompute with a sieve instead.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Sieve of EratosthenesPrecompute all primes ≤ N once in O(N log log N) when many queries share a bounded range.
- Segmented SieveFind primes in a high range [L, R] using primes up to √R — the same √n insight at scale.
- GCD of Two NumbersAnother number-theory staple where the right insight beats brute iteration.