← Create New Paste

Counting Primes in a Coding Interview: How to Present the Sieve of Eratosthenes

3 views
"Count the prime numbers less than n" looks like a warm-up question, but interviewers use it to see whether you can move from a brute-force idea to an efficient algorithm and explain why it works. Here is a structured way to walk through it out loud. Step 1: Start with the naive check The obvious approach tests each number k from 2 to n-1 for primality by trying every divisor up to the square root of k. Say this first, and give the cost: roughly O(n * sqrt(n)). Mentioning the square-root bound already shows you know a useful fact: if k has a divisor larger than sqrt(k), it must also have one smaller than sqrt(k). Step 2: Flip the problem around Instead of asking "is this number prime?" for every number, ask "which numbers are definitely not prime?" Every composite number is a multiple of some smaller prime. So if you walk through the primes in order and cross out their multiples, whatever is left uncrossed is prime. That is the Sieve of Eratosthenes, and saying the idea in one sentence before you write code helps the interviewer follow you. Step 3: Write the sieve Create a boolean array is_prime of size n, set everything to true, then mark 0 and 1 as false. For each i starting at 2 while i * i < n: if is_prime[i] is still true, mark i*i, i*i + i, i*i + 2i, and so on as false. At the end, count the true entries. Two details are worth pointing out as you code: - The outer loop can stop at sqrt(n), because any composite number below n has a prime factor no larger than sqrt(n). - The inner loop can start at i*i rather than 2*i, because smaller multiples of i were already crossed out by smaller primes. Step 4: State the complexity Time is O(n log log n), which grows so slowly that it behaves almost linearly in practice. Space is O(n) for the array. If the interviewer pushes on memory, you can mention a bitset (one bit per number) or skipping even numbers to halve the array. Step 5: Test edge cases out loud Check n = 0, 1 and 2 (all should return 0, since the question asks for primes strictly less than n). Then try n = 10 and confirm you get 4 (2, 3, 5, 7). Be clear about "less than n" versus "less than or equal to n". Off-by-one mistakes here are the most common reason a correct idea fails the tests. Follow-up questions to expect - Segmented sieve: how would you find primes in a range like [10^9, 10^9 + 10^6] without allocating 10^9 booleans? (Sieve the small primes up to sqrt of the upper bound, then use them to cross out multiples inside the window.) - Smallest prime factor sieve: store the smallest prime factor for each number so you can factorize any number below n quickly. - Why not just run Miller-Rabin on each number? Good for testing one huge number, wasteful for counting all primes below n. Practising the explanation Like most interview questions, the code is only half the score. The other half is narrating your reasoning: naive approach, key insight, optimisation, complexity, tests. Practise that sequence until it feels natural. If live coding rounds make you freeze even when you know the material, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, so you can keep your explanation structured while you work through problems like this one.
Created Nov 17, 2026 01:46 Expires Nov 17, 2027 01:46