Count Primes — Sieve of Eratosthenes O(n log log n) [Amazon Easy]

Problem Statement#

Given an integer n, return the number of prime numbers strictly less than n.

Example 1:

Input:  n = 10
Output: 4
Explanation: 2, 3, 5, 7 are the four primes less than 10.

Example 2:

Input:  n = 0
Output: 0

Example 3:

Input:  n = 1
Output: 0

Constraints: 0 <= n <= 5 * 10^6

Why This Problem Matters#

Count Primes is not really an array problem. It is a math-meets-algorithms problem disguised as an easy LeetCode question. Amazon tags it as Easy — and technically the brute-force solution is easy to write. The catch is that with n up to 5,000,000, a naive primality check is catastrophically slow. You will write code that looks correct, submit it, and watch it time out. That is the trap. That is what the interview is actually testing.

The reason this problem appears in FAANG loops is that it checks whether you know a specific classical algorithm: the Sieve of Eratosthenes. This algorithm is over 2,000 years old, attributed to the Greek mathematician Eratosthenes of Cyrene, and it remains one of the most efficient methods for finding all primes up to a given limit. If you know it, you can write a clean, optimal solution in under 5 minutes. If you do not, you will either submit a TLE solution or spend the interview trying to rediscover 2,000 years of number theory under pressure.

Beyond the interview, the Sieve is a foundational tool that powers problems involving prime factorization, smallest prime factors, counting divisors, and generating prime ranges. Knowing it deeply — not just the code, but the reasoning — unlocks an entire class of problems.

The Core Insight — Sieve of Eratosthenes#

Before touching code, let us understand what the Sieve actually does and why it works.

The naive approach for checking if a number k is prime: try dividing it by every number from 2 to k - 1. If nothing divides it, it is prime. To count primes up to n, you do this for every number. Time complexity: O(n * sqrt(n)) in the optimized version (checking divisors up to sqrt(k)), which is still way too slow for n = 5,000,000.

The Sieve's key observation: Instead of asking "for each number, is it prime?", flip the question: "for each known prime, which numbers does it immediately eliminate?"

Here is the idea step by step.

Start with the assumption that every number from 2 to n - 1 is prime. Create a boolean array called is_prime of size n, all initialized to True.

Now take the first prime, 2. Every multiple of 2 — 4, 6, 8, 10, ... — cannot be prime (they are all divisible by 2). Mark them all False. Do not mark 2 itself.

Move to the next number that is still True: 3. It is prime (nothing has crossed it out yet). Now mark all multiples of 3 — 6, 9, 12, 15, ... — as False.

Continue: 4 is already False (crossed out by 2), skip it. 5 is still True, it is prime. Mark multiples of 5 — 25, 30, 35, ... — as False. Notice we start at 25, not 10. Why?

The crucial optimization: start marking from p * p, not from 2 * p.

When you arrive at prime p, every multiple of p that is smaller than p * p has already been marked by a smaller prime. For example, when p = 5:

• 5 * 2 = 10 was already marked when we processed prime 2
• 5 * 3 = 15 was already marked when we processed prime 3
• 5 * 4 = 20 was already marked when we processed prime 2

So the first multiple of 5 that has not yet been marked is 5 * 5 = 25. Starting there saves a significant amount of work.

You only need to run the outer loop up to sqrt(n). Any composite number less than n must have at least one prime factor that is <= sqrt(n), so by the time the outer loop finishes, all composite numbers are already marked.

At the end, count the indices that are still True. That count is your answer.

This produces a time complexity of O(n log log n) — asymptotically nearly linear, and fast enough for n = 5,000,000 in milliseconds.

Visual Dry Run#

Let us trace the sieve for n = 20 (finding all primes less than 20) step by step.

Initial state — all assumed prime:

Index:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
is_prime:F  F  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T

(Indices 0 and 1 are manually set to False — 0 and 1 are not prime by definition.)

Iteration 1 — p = 2 (is_prime[2] is True, so 2 is prime):

Start marking from p * p = 4. Mark 4, 6, 8, 10, 12, 14, 16, 18 as False.

Index:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
is_prime:F  F  T  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T
                     ^     ^     ^     ^     ^     ^     ^     ^
                  marked composite by prime 2

Iteration 2 — p = 3 (is_prime[3] is True, so 3 is prime):

Start marking from p * p = 9. Mark 9, 12, 15, 18 as False. (12 and 18 already False, no harm.)

Index:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
is_prime:F  F  T  T  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T
                              ^           ^     ^
                          marked composite by prime 3

Iteration 3 — p = 4 (is_prime[4] is False — already composite, skip).

Iteration 4 — p = 5 (is_prime[5] is True, so 5 is prime):

p * p = 25, which is >= n = 20. No marks needed. The outer loop ends here because sqrt(20) is approximately 4.47, so we stop after checking up to p = 4.

Final state:

Index:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
is_prime:F  F  T  T  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T

Counting the True values: indices 2, 3, 5, 7, 11, 13, 17, 19 — that is 8 primes.

Common Mistakes#

These are the real mistakes that real candidates make in interviews under time pressure — not hypothetical edge cases, but thinking errors that surface in the middle of coding.

Mistake 1: Using trial division per number instead of the Sieve.

The most common mistake is writing a helper is_prime(k) function and calling it for every number from 2 to n - 1. This looks like:

def countPrimes(n):
    count = 0
    for k in range(2, n):
        if all(k % d != 0 for d in range(2, int(k**0.5) + 1)):
            count += 1
    return count

This is O(n * sqrt(n)) — technically correct, but it times out for n = 5,000,000. The LeetCode constraint is specifically chosen to reject this approach. In an interview, if you write this and the interviewer says "can you make it faster?", you need to know the Sieve immediately. If you do not, the rest of the interview is damage control.

Mistake 2: Starting to mark multiples from 2 * p instead of p * p.

A candidate who almost knows the Sieve but misremembers it writes:

for j in range(2 * i, n, i):   # WRONG — should be i * i
    is_prime[j] = False

This still produces the correct answer — it just does extra redundant work. For small n you will not notice. For n = 5,000,000 it is noticeably slower. More importantly, when an interviewer asks "why do you start at p * p?", you need to be able to explain it: all smaller multiples were already marked by earlier primes. If you started at 2 * p, you cannot explain your own code. That is a red flag in a senior interview.

Mistake 3: Running the outer loop up to n instead of sqrt(n).

The outer loop only needs to go up to sqrt(n):

for i in range(2, int(n**0.5) + 1):   # correct
for i in range(2, n):                   # wasteful but still correct

The second version is still correct (you just check numbers that have no more composite multiples to mark), but it is O(n) extra iterations of a loop that does nothing. An interviewer who knows their stuff will catch this and ask why you are iterating all the way to n. Being able to explain the sqrt(n) bound — "any composite number k < n must have a prime factor <= sqrt(n), so once we have processed all primes up to sqrt(n), all composites are already marked" — is the answer that separates a pass from a borderline.

Mistake 4: Off-by-one on the array size or the loop bound.

The problem says "strictly less than n". So you need primes in the range [2, n-1]. The array should be of size n (indices 0 through n-1). If you make it size n + 1 or n - 1 you either waste a cell or access an out-of-bounds index. Similarly, not handling n < 2 before initializing the array causes index errors when n = 0 or n = 1.

Mistake 5: Forgetting that 0 and 1 are not prime.

After creating the is_prime array of all True, you must explicitly set is_prime[0] = False and is_prime[1] = False. If you forget, you will count them as primes. This is easy to overlook when you are focused on the sieve logic and is a silent bug — the code runs but returns wrong answers.

Solutions#

Approach 1 — Brute Force: Trial Division O(n * sqrt(n))#

For each number, check if anything divides it. Correct but too slow for large n.

Python

class Solution:
    def countPrimes(self, n: int) -> int:
        # Handle edge cases: no primes exist below 2
        if n < 2:
            return 0
 
        def is_prime(k: int) -> bool:
            # 2 is the smallest prime; 0 and 1 are not prime
            if k < 2:
                return False
            # Only check divisors up to sqrt(k) — if k has a factor
            # larger than sqrt(k), it must also have one smaller than sqrt(k)
            for d in range(2, int(k ** 0.5) + 1):
                if k % d == 0:
                    return False  # found a divisor, not prime
            return True
 
        # Count how many integers in [2, n-1] are prime
        count = 0
        for k in range(2, n):
            if is_prime(k):
                count += 1
        return count

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
function countPrimes(n) {
    // Handle edge cases: no primes exist below 2
    if (n < 2) return 0;
 
    // Check whether a single number k is prime
    function isPrime(k) {
        if (k < 2) return false;
        // Only check divisors up to sqrt(k)
        for (let d = 2; d * d <= k; d++) {
            if (k % d === 0) return false; // divisible, not prime
        }
        return true;
    }
 
    // Count integers in [2, n-1] that are prime
    let count = 0;
    for (let k = 2; k < n; k++) {
        if (isPrime(k)) count++;
    }
    return count;
}

Approach 2 — Sieve of Eratosthenes O(n log log n) — Optimal#

Mark composite numbers in bulk rather than checking each number individually.

Python

class Solution:
    def countPrimes(self, n: int) -> int:
        # No primes exist below 2
        if n < 2:
            return 0
 
        # Create a boolean array; index i represents whether i is prime.
        # bytearray is more memory-efficient than a Python list of booleans.
        # Initialize everything to 1 (True = prime).
        is_prime = bytearray([1]) * n
 
        # 0 and 1 are not prime by definition
        is_prime[0] = 0
        is_prime[1] = 0
 
        # Only need to run the outer loop up to sqrt(n).
        # Any composite number less than n has a prime factor <= sqrt(n),
        # so all composites will be marked by the time we reach sqrt(n).
        i = 2
        while i * i < n:
            if is_prime[i]:
                # Start marking from i*i — all smaller multiples of i
                # were already marked by primes smaller than i.
                # Slice assignment is O(n/i) and very fast in Python.
                is_prime[i * i :: i] = bytearray(len(is_prime[i * i :: i]))
            i += 1
 
        # Sum the array: each 1 represents a prime number
        return sum(is_prime)

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
function countPrimes(n) {
    // No primes exist below 2
    if (n < 2) return 0;
 
    // Uint8Array is more memory-efficient than a plain JS array.
    // Fill with 1 (True = assumed prime) for every index.
    const isPrime = new Uint8Array(n).fill(1);
 
    // 0 and 1 are not prime by definition
    isPrime[0] = 0;
    isPrime[1] = 0;
 
    // Outer loop only needs to go up to sqrt(n)
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            // Start marking composites from i*i.
            // All multiples below i*i were already handled by smaller primes.
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = 0; // mark as composite
            }
        }
    }
 
    // Count remaining 1s — these are the primes
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

Complexity Analysis#

Why O(n log log n)? The total work done by the Sieve is proportional to the sum of n/p for each prime p <= n. By the prime harmonic series, this sum converges to n * log(log(n)). In practice, for n = 5,000,000, this is roughly 75 million operations — well within time limits.

Space trade-off: The Sieve uses O(n) extra memory to store the boolean array. For n = 5,000,000, a bytearray in Python uses 5 MB and a Uint8Array in JavaScript uses 5 MB. This is the cost of near-linear time — you buy speed by paying in memory.

Memory optimization note: A bitset sieve represents each number as a single bit rather than a byte, reducing space to O(n/8). For n = 5,000,000 that is around 625 KB. This is worth mentioning if the interviewer asks about memory constraints.

Follow-up Questions#

These are the actual escalations that interviewers at Google, Amazon, and Bloomberg follow up with after you implement the basic Sieve.

Q1: What if you need to count primes in a range [L, R] where both L and R can be up to 10^12, but the range R - L is at most 10^6?

A standard Sieve up to 10^12 is impossible — you cannot allocate that much memory. The answer is the Segmented Sieve. First, run a standard Sieve up to sqrt(R) (at most about 10^6) to find all small primes. Then, for the range [L, R], create a small boolean array of size R - L + 1. For each small prime p, mark all its multiples that fall within [L, R] as composite. Count what remains. This is O(sqrt(R) + (R - L) * log(log(R))) time and O(sqrt(R) + (R - L)) space.

Q2: What if you need the prime factorization of every number up to n efficiently?

Modify the Sieve to store the smallest prime factor (SPF) for each number instead of just a boolean. During the Sieve, when you first mark a composite j from prime i, record spf[j] = i if spf[j] has not been set yet. Then to factorize any number k, repeatedly divide by spf[k] until k = 1. Each factorization takes O(log k) time instead of O(sqrt(k)). This is a critical optimization when you need to factorize many numbers in one pass.

Q3: Can you find the nth prime efficiently?

The Sieve directly gives you all primes in sorted order — just collect them into an array during the counting step. Finding the nth prime is then an O(1) array lookup. The challenge is choosing n large enough for the Sieve. By the Prime Number Theorem, the nth prime is approximately n * ln(n), so you can pre-compute an upper bound and run the Sieve up to that bound.

Q4: How would you handle the problem if memory is extremely constrained?

If O(n) space is not acceptable, discuss the trade-offs honestly. The Sieve of Sundaram can find all odd primes up to a limit using roughly half the space. A bitset implementation of the standard Sieve reduces space by a factor of 8. If you need to go further, the Segmented Sieve with a sliding window can use O(sqrt(n)) space while still achieving near-linear time. These are not common interview requirements, but knowing they exist signals you have thought beyond the textbook solution.

Q5: What if n is given as a string (arbitrarily large number)?

This shifts the problem entirely. You cannot run the Sieve on an arbitrarily large n — you would use the Prime Counting Function (π(n)), which is a deep number theory topic. In an interview, acknowledging the complexity and explaining the Segmented Sieve approach for tractable ranges is the right answer. You are not expected to implement the full Meissel-Mapes algorithm on a whiteboard.

This Pattern Solves#

The Sieve of Eratosthenes is not a one-trick solution. Once you understand it, you can adapt it to solve a broader family of problems:

• LeetCode 204 — Count Primes: the direct problem
• LeetCode 952 — Largest Component Size by Common Factor: build a union-find keyed on prime factors, use SPF sieve
• LeetCode 2523 — Closest Prime Numbers in Range: enumerate primes in a range using the Sieve, then find the closest pair
• LeetCode 279 — Perfect Squares: sieve-like DP where you precompute all squares and build up answers
• LeetCode 263 / 264 — Ugly Numbers: prime factorization logic closely related to the Sieve's marking step

The deeper skill being tested in all of these is the same: when you have a number-theoretic property that can be propagated to multiples (or factors), the Sieve structure — initialize all, then mark in bulk — is the right tool.

Key Takeaways#

• LeetCode 204 — Count Primes is a Medium-difficulty Easy problem asked at Amazon and Bloomberg; it tests knowledge of the Sieve of Eratosthenes.
• The Sieve runs in O(n log log n) time — far better than the naive O(n sqrt(n)) trial division — by propagating composite information outward from each prime.
• The outer loop only needs to go to sqrt(n) because any composite n has at least one factor at or below its square root.
• Start marking multiples at p * p (not 2 * p) because all smaller multiples k*p where k < p were already marked by an earlier prime k.
• Space is O(n) for the boolean sieve array — this is the trade-off versus the O(1) space trial division approach.
• Explaining both optimizations (loop to sqrt(n), start at p*p) in an interview is the difference between a pass and a strong hire signal.
• The sieve pattern generalizes to "mark multiples" problems — factorization, smallest prime factor tables, and number theory problems on LeetCode.