How would you check whether a single number is prime, and if you instead needed every prime up to some limit n, would your approach change?
technical-conceptual · Junior level · software-engineering
What the interviewer is really asking
Assesses whether the candidate knows the sqrt(n) trial-division bound for testing one number, recognizes that 'all primes up to n' calls for the Sieve of Eratosthenes instead, and can compare the two by cost.
What to say
- For a single number, do trial division but only up to the square root of n — if n has a factor larger than its square root, the matching cofactor is smaller than the square root, so you'd have already found it. That makes the test O(sqrt(n)).
- Add the easy optimizations: handle 2 separately, then only test odd divisors (or 2 and 3 then 6k±1), and return early on the first divisor found.
- Switch algorithms for 'all primes up to n': the Sieve of Eratosthenes marks multiples of each prime starting from p*p, running in about O(n log log n) total — far better than calling an O(sqrt(n)) test n separate times.
What to avoid
- Trial-divide all the way up to n instead of stopping at its square root — that's a needless O(n) per number when O(sqrt(n)) suffices.
- Run the single-number primality test n times in a loop to list all primes up to n when a sieve is dramatically faster.
- Forget the edge cases: numbers less than 2 aren't prime, and 2 is the only even prime.
Example answers
Strong: For one number n, I trial-divide only up to sqrt(n): if there were a factor above the square root, its cofactor would be below it and I'd have caught that first — so testing past the root is wasted work. That's O(sqrt(n)). I'd special-case n < 2 as not prime, check 2, then only try odd divisors. For all primes up to a limit, I'd switch to the Sieve of Eratosthenes — start with everything marked prime, then for each prime p cross off multiples from p*p upward. It runs in roughly O(n log log n), which crushes calling the single-number test n times.
Weak: I'd loop from 2 up to n and check if any of them divides it evenly — if none do, it's prime.