Check whether a number is prime by testing divisors only up to √n — O(√n) instead of O(n). See the speed difference live in your browser.
The problem
Return True if n is a prime number. Numbers below 2 are not prime.
Examples
Example 1
Input
is_prime(7)
Expected output
True
Example 2
Input
is_prime(10)
Expected output
False
+ 6 hidden tests on Submit.
Edge cases to ask about
- 0, 1, 2
- Even numbers
- Perfect squares like 49
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Try every divisor below n | O(n) | O(1) | Test every integer from 2 to n - 1. |
| bestDivisors up to √n | O(√n) | O(1) | If n = a × b, min(a, b) ≤ √n. Check 2, then odd numbers up to √n. |
Walkthrough of the optimal approach (try it yourself first)
A prime number is an integer greater than 1 with no positive divisors other than 1 and itself.
Why testing up to $\sqrt{n}$ is sufficient
If $n$ is composite, it can be factored as $n = a \times b$. Both factors cannot be strictly greater than $\sqrt{n}$, because then $a \times b > \sqrt{n} \times \sqrt{n} = n$. Therefore, at least one factor must be $\le \sqrt{n}$. If no divisor divides $n$ up to $\sqrt{n}$, $n$ is guaranteed to be prime.
Optimization steps
- Handle base cases: Numbers $< 2$ are not prime. $2$ is the only even prime.
- Eliminate even numbers: Any other even number (
n % 2 == 0) is composite. - Odd divisors only: Starting at $i = 3$, test only odd numbers ($i \gets i + 2$) while $i \times i \le n$. This halves the operations from $\sqrt{n}$ to $\approx \frac{\sqrt{n}}{2}$.
For $n = 1,000,000,000$, naive trial division requires 1 billion iterations. Testing odd divisors up to $\sqrt{n}$ takes about 16,000 checks.
Complexity: O(√n) time, O(1) space. If n has a divisor bigger than √n, it also has a matching one smaller than √n, so checking up to √n is enough.
Reveal the reference solution
def is_prime(n): if n < 2: return False if n % 2 == 0: return n == 2 i = 3 while i * i <= n: if n % i == 0: return False i += 2 return True
The brute force, for comparison
def is_prime(n): if n < 2: return False for i in range(2, n): if n % i == 0: return False return True
Follow-ups interviewers ask
- Why is i * i <= n better than i <= math.sqrt(n)?
- How does the Sieve of Eratosthenes find all primes below n in O(n log log n)?
- How can the 6k ± 1 optimization reduce checks by an additional 33%?
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Check If a Number Is Prime in Python?
The optimal solution runs in O(√n) time and O(1) auxiliary space. If n has a divisor bigger than √n, it also has a matching one smaller than √n, so checking up to √n is enough.
What is the brute-force approach, and how do you optimise it?
Try every divisor below n: O(n) time, O(1) space. Test every integer from 2 to n - 1. Divisors up to √n: O(√n) time, O(1) space. If n = a × b, min(a, b) ≤ √n. Check 2, then odd numbers up to √n.
What follow-up questions do interviewers ask about Check If a Number Is Prime in Python?
Why is i * i <= n better than i <= math.sqrt(n)? How does the Sieve of Eratosthenes find all primes below n in O(n log log n)? How can the 6k ± 1 optimization reduce checks by an additional 33%?