Count Primes

Free with account Updated Nov 19, 2026 · 5 min read
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

    Below 30 there are 10 primes. n itself is never counted, so the answer for n = 7 is 3 (2, 3 and 5).
    Below 30 there are 10 primes. n itself is never counted, so the answer for n = 7 is 3 (2, 3 and 5).
    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

    1. Strictly less than n, or up to and including n? (Here: strictly less.)
    2. How large can n get? It decides between the sieve (memory O(n)) and something smarter.
    3. Will there be many queries for different n? Then sieve once up to the largest n and keep a prefix count.