Count Primes
On this page
Problem statement
Given an integer n, return how many prime numbers are strictly less than n. A prime is an integer greater than 1 whose only divisors are 1 and itself. n can be as large as 5 million.
Short to state, and the expected answer is a 2,000-year-old algorithm: the Sieve of Eratosthenes. Interviewers use it to check whether you know it, can explain why it's fast, and get its two loop bounds right. Original problem: LeetCode 204.
Example

Input: n = 30
Output: 10 # 2 3 5 7 11 13 17 19 23 29
Input: n = 7 -> 3 # 7 itself is not counted
Input: n = 2 -> 0
Input: n = 0 -> 0
Constraints (assumed)
- 0 ≤ n ≤ 5 × 10⁶.
What this question tests
- Knowing the sieve and why it beats testing each number on its own.
- The two bounds: start crossing at p², and stop when p² ≥ n.
- Reading "less than n" carefully.
Questions to ask first
- Strictly less than n, or up to and including n? (Here: strictly less.)
- How large can n get? It decides between the sieve (memory O(n)) and something smarter.
- Will there be many queries for different n? Then sieve once up to the largest n and keep a prefix count.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.