Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return false for n ≤ 1. Then check divisors `i` from 2 while `i*i ≤ n`; if any divides n it's composite. Stopping at √n is the key optimisation.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know the √n divisor bound and justify it, plus the base cases.
Where candidates slip
An O(n) loop, or mishandling 0/1, or i*i overflow.
How to stand out
Explain the divisor-pairing argument for √n and mention the Sieve of Eratosthenes for many queries.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
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 1 · Optimal
Trial division to √n
1Hint 1Explore hintHide hint
Try dividing n by candidates starting at 2 — but how far do you really need to go?
2Hint 2Explore hintHide hint
Divisors pair up around √n, so you only need to test up to √n.
3Hint 3Explore hintHide hint
Use `i * i <= n` (integer-safe) and handle n ≤ 1 as 'not prime' first.
A · Core idea
A prime is an integer greater than 1 whose only divisors are 1 and itself. Test candidate divisors from 2 upward; if none divides n, it's prime. The key optimisation is stopping at √n.
Why √n is enough. Divisors come in pairs: if d divides n, so does n/d. One member of each pair is ≤ √n and the other is ≥ √n. So if n had any divisor, it would have one at or below √n — checking past √n only re-finds the larger partners. This turns an O(n) scan into O(√n).
Why `i * i <= n` instead of `i <= sqrt(n)`. Squaring keeps you in integer arithmetic and avoids floating-point rounding errors near perfect squares. Cast to long for the square ((long) i * i) so it can't overflow int for large n.
The base cases. n ≤ 1 (including 0, 1, and negatives) is not prime by definition — handle that before the loop. 2 and 3 fall through correctly because the loop body never finds a divisor.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 37i = 2
37 % 2 = 1
no divisortrueC · Code with teaching comments
D · Why it works and complexityO(√n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The √n cutoff is the whole interview point — an O(n) divisor loop is the giveaway that you haven't seen the trick.
ComplexityO(√n) time, O(1) space — the loop runs until i² exceeds n, i.e. about √n iterations, each doing one modulo.
E · Edge cases and pitfalls6n = 1 — Not prime by definition — handled before the loop.Explore edge casesHide edge cases
Edge cases handled
n = 1Not prime by definition — handled before the loop.n = 2Loop's first square 4 > 2, so it exits immediately → prime.n = 9i = 3 divides it (3×3) → not prime, caught at √9.
Pitfalls
- Looping all the way to n (O(n)) instead of √n.
- Marking 0 or 1 as prime.
- `i * i` overflowing int for large n — cast to long.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; (long) i * i <= n; i++) { if (n % i == 0) return false; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Scanning every divisor up to n
Checking i from 2 to n−1 is O(n); on n near 10⁹ it times out. Divisors pair around √n, so √n suffices.
Explore the code comparisonHide the code comparison
Scanning every divisor up to n
Checking i from 2 to n−1 is O(n); on n near 10⁹ it times out. Divisors pair around √n, so √n suffices.
Don't write this
for (int i = 2; i < n; i++) if (n % i == 0) return false;Write this instead
for (int i = 2; (long) i * i <= n; i++) if (n % i == 0) return false;Revise
Carry the pattern into the interview
Pattern to remember
Trial division to √n
Code pattern to memorize
for i=2 while i*i<=n: if n%i==0 -> compositeRules to remember
- 1n ≤ 1 → not prime.
- 2Check i from 2 while i·i ≤ n.
- 3Any divisor ⟹ composite.
Use this pattern when
- Primality / divisor questions
- Anytime you can bound a search at √n
Choose another pattern when
- Many primality queries — precompute a sieve instead
Interview takeaway
Factors come in pairs around √n — never scan past it.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA core fresher pattern: Trial division to √n. Master it on small inputs and it transfers to harder problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Count Primes (sieve)Coming soonSieve of Eratosthenes counts all primes below n in O(n log log n).