Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

• Difficulty: MEDIUM
• Problem: Count Primes
• Topics: Array, Math, Enumeration, Number Theory

Problem gist

Given an integer n, the task is to count how many prime numbers are strictly smaller than n. A prime is an integer greater than one whose only positive divisors are one and itself. The word strictly matters: if n is prime, n is not included in the answer.

Checking every candidate independently is wasteful. Trial division can determine whether one number is prime, but repeating it for every value below n performs much of the same work again. The better perspective is to identify composite numbers in bulk.

Deriving the sieve

Start by tentatively treating every number from 2 through n - 1 as prime. When a surviving number p is encountered, cross out all multiples of p, because none of them can be prime. After all necessary crossings-out, the flags that remain set correspond exactly to the primes below n.

There are two details that make this efficient:

1. Marking can begin at p * p. Every smaller multiple of p has another factor smaller than p, so it was already crossed out when that factor was processed.
2. Candidate factors only need to run through the square root of n - 1. Any composite below n has at least one factor no larger than its square root, so a larger factor cannot reveal a new composite.

This is the Sieve of Eratosthenes. Its time complexity is O(n log log n), and its space complexity is O(n). The implementation uses a bytearray rather than a Python list of booleans so that each flag occupies one byte and blocks of multiples can be cleared efficiently.

Python solution

from math import isqrt


class Solution:
    def countPrimes(self, n: int) -> int:
        """Return the number of prime integers strictly smaller than n."""
        if n <= 2:
            return 0

        prime_flags = self._build_prime_flags(n)
        return sum(prime_flags)

    @staticmethod
    def _build_prime_flags(limit: int) -> bytearray:
        """Build flags where index k is 1 exactly when k is prime."""
        prime_flags = bytearray(b"\x01") * limit
        prime_flags[0:2] = b"\x00\x00"

        # Every composite below limit has a factor at most sqrt(limit - 1).
        largest_factor_to_check = isqrt(limit - 1)
        for candidate in range(2, largest_factor_to_check + 1):
            if not prime_flags[candidate]:
                continue

            # Smaller multiples already have a smaller prime factor and were
            # cleared earlier, so candidate squared is the first new one.
            first_composite = candidate * candidate
            composite_count = (
                (limit - 1 - first_composite) // candidate
            ) + 1
            prime_flags[first_composite:limit:candidate] = (
                b"\x00" * composite_count
            )

        return prime_flags

The helper isolates construction of the sieve from the counting operation. The slice assignment performs the same logical marking as a loop over candidate * candidate, candidate * candidate + candidate, ..., but it lets optimized byte-array operations do the repetitive work.

Interview follow-ups

Why is it safe to start crossing out at p * p?

Any smaller multiple of p can be written as p * k where k < p. If k is greater than one, that multiple was already crossed out when the algorithm processed a prime factor of k. Starting at p * p therefore skips only work that has already been done; it does not skip a composite that could still be marked as prime. This optimization preserves the sieve’s result while reducing duplicate writes.

Can the memory usage be reduced when only the count is needed?

Yes. Except for 2, every even number is composite, so an odd-only sieve can store one flag for each odd candidate and cut the main array roughly in half. Index i can represent the value 2 * i + 1, with marking adjusted to that mapping. The asymptotic bounds remain O(n log log n) time and O(n) space, but the constant-factor memory savings are meaningful. The tradeoff is more index arithmetic and a greater chance of off-by-one errors.

What if n is too large for one sieve array?

A segmented sieve handles the range in fixed-size blocks. First, compute all primes through sqrt(n - 1). For each later segment, allocate flags only for that segment and use the base primes to mark its composites, then add the surviving count before reusing the buffer for the next segment. The time remains close to O(n log log n), while working memory becomes O(sqrt(n) + B) for segment size B. This approach adds bookkeeping but also improves cache locality and makes very large bounds practical.

Can the algorithm run in linear time?

Euler’s linear sieve maintains a growing list of discovered primes and marks each composite using its smallest prime factor exactly once. That gives O(n) worst-case time and O(n) space. It is a strong answer when the interviewer explicitly asks for a linear sieve or also wants smallest-prime-factor information. For a single prime-count query, the Sieve of Eratosthenes is usually preferable because it is simpler and often has smaller real-world constants.

How should repeated queries be answered efficiently?

If many queries have bounds at most some known maximum, build one sieve through that maximum and create a prefix array where position i stores the number of primes below i. The preprocessing costs O(M log log M) time and O(M) space for maximum bound M, after which every query is answered in O(1) time. If the maximum is unknown and grows over time, the service can rebuild geometrically or maintain segmented results, trading implementation complexity for less repeated work.

How would the solution change if the caller needs the primes themselves?

The sieve construction does not change. Instead of summing the flags, scan them and collect every index whose flag is set. The sieve still costs O(n log log n) time and O(n) auxiliary space, while producing the result adds O(n) scanning time and O(pi(n)) output space, where pi(n) is the number of primes below n. Output space cannot be avoided when all primes must be returned.