LeetCode 204 – Count Primes

Count Primes is a problem about knowing an algorithm. There is no insight to derive under pressure — either the Sieve of Eratosthenes is in your head or it is not — and what is actually being tested is the two optimisations that make it fast enough, plus whether you can say why they are correct.

The problem

Return the number of prime numbers strictly less than n.

n = 10  -> 4      2, 3, 5, 7
n = 0   -> 0
n = 1   -> 0
n = 2   -> 0      strictly less than 2, so 2 itself does not count
n = 3   -> 1      just 2

Strictly less than. n = 2 returning 0 rather than 1 is the boundary, and it is the first thing to check any implementation against.

Why trial division is not enough

Testing each number for primality by dividing up to its square root is O(n √n). For n = 5,000,000 — LeetCode's limit — that is far too slow, and the constraint exists precisely to rule it out.

The sieve inverts the question. Instead of asking "is k prime?" for each k, it starts from "everything is prime" and crosses off every multiple of every prime it finds. Each composite gets crossed off once per distinct prime factor, which is what makes the total work nearly linear.

The two optimisations

Stop the outer loop at √n. If k is composite it has a factor no larger than √k, so it will already have been crossed off by the time the outer loop reaches √n. Continuing past that point finds nothing new.

Start the inner loop at p × p, not 2 × p. Every smaller multiple — 2p, 3p, up to (p−1)p — has a factor below p and was therefore already crossed off when that smaller factor was processed. Starting at p² skips all of that duplicated work.

p = 5:   10, 15, 20  already crossed by 2 and 3
         start at 25

Both are corollaries of the same fact — a composite's smallest prime factor is at most its square root — and being able to state that once, then derive both, is the answer.

Java

class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;              // no primes below 2, and 2 itself is excluded

        boolean[] composite = new boolean[n];   // false = still assumed prime

        // Beyond sqrt(n) every composite already has a smaller factor recorded.
        for (int p = 2; (long) p * p < n; p++) {
            if (composite[p]) continue;         // p is not prime, skip it

            // Multiples below p*p were crossed off by p's smaller factors.
            for (int multiple = p * p; multiple < n; multiple += p) {
                composite[multiple] = true;
            }
        }

        int count = 0;
        for (int k = 2; k < n; k++) {
            if (!composite[k]) count++;
        }
        return count;
    }
}

(long) p * p < n rather than p * p < n. For n near Integer.MAX_VALUE the product overflows to a negative number, the condition stays true, and the inner loop then indexes with a negative multiple. The cast costs nothing and prevents a crash that only appears at the top of the range.

The array tracks composite rather than prime, so the default false means "assumed prime" and no initialisation pass is needed. Naming it for what it stores rather than for what you want keeps the polarity straight — isPrime initialised to false is a classic self-inflicted bug.

Python

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0

        composite = [False] * n          # False = still assumed prime

        for p in range(2, int(n ** 0.5) + 1):
            if composite[p]:
                continue

            # Slice assignment crosses off the whole arithmetic progression at once.
            composite[p * p::p] = [True] * len(range(p * p, n, p))

        return composite[2:].count(False)

composite[p*p::p] = [True] * len(...) is the idiomatic Python sieve: extended slice assignment writes the entire progression in C rather than looping in the interpreter, which is a large constant-factor win at this scale.

int(n ** 0.5) + 1 uses floating point, which is fine for LeetCode's bound but drifts for very large n. math.isqrt(n) is exact and is the better habit — the same concern as Sqrt(x).

Complexity

log log n is under 3 for any n that fits in memory, so the sieve is effectively linear. The bound comes from summing n/p over the primes p below n, and that sum is n log log n by Mertens' theorem — worth naming even if you would not derive it.

The O(n) space is the real cost, and it is what the follow-up usually probes: a segmented sieve processes fixed-size windows and needs only O(√n), which is how you count primes below 10¹². A bitset instead of a boolean array cuts the constant by eight.

What the interviewer is checking

• That you reach for the sieve rather than trial division, and know why the constraint forces it.
• The outer loop stopping at √n, with the reason.
• The inner loop starting at p², with the reason.
• n = 0, 1, 2 — strictly less than.
• The overflow in p * p near the integer limit.
• That the array's polarity is stated, not assumed.
• O(n log log n), and that the space is the thing worth improving.