Count Primes Solution

Problem

Count how many prime numbers exist that are strictly less than a given integer n. A prime is any integer greater than 1 that is divisible only by 1 and itself.

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

Counter-example: n = 2 → output 0. There are no primes below 2, since 2 itself is not "strictly less than" 2.

Intuition

For a small input you could test each number individually, but verifying every candidate up to n is expensive. The key insight is that once you confirm a number p is prime, every multiple of p — other than p itself — is guaranteed composite. Instead of asking "is this number prime?" one at a time, you can batch-eliminate all composites at once. Starting that elimination at p² (not 2p) is the critical optimization: every smaller multiple k × p where k < p was already crossed out when you processed the prime k.

Approach 1 — Brute Force

For each candidate from 2 to n − 1, trial-divide it by every integer up to its square root. If no divisor divides evenly, the candidate is prime.

Define a helper that checks if num is prime
Loop divisor from 2 to floor(√num); return False on any clean division
If no divisor divides evenly, return True
Count each prime candidate in range(2, n) and return the total

1def countPrimes(n: int) -> int:
2    def is_prime(num):
3        if num < 2:
4            return False
5        # only check up to sqrt(num): any factor above sqrt pairs with a smaller factor below it
6        for divisor in range(2, int(num**0.5) + 1):
7            if num % divisor == 0:
8                return False
9        return True
10
11    count = 0
12    for candidate in range(2, n):  # range stops before n: problem asks for primes strictly less than n
13        if is_prime(candidate):
14            count += 1
15    return count

Time: O(n√n) — for each of the n candidates we do up to √n division checks.
Space: O(1) — just a counter; no extra array.

Approach 2 — Sieve of Eratosthenes

Allocate a boolean array for every integer below n, initialize all to "prime", then cross off composites in bulk each time a prime is found.

Return 0 immediately if n ≤ 2 — no primes exist below 2
Initialize is_prime[0..n-1] to True; set indices 0 and 1 to False
For i from 2 while i * i < n:
If is_prime[i] is True, mark every multiple of i starting at i * i as False
Count and return all remaining True entries

1def countPrimes(n: int) -> int:
2    if n <= 2:
3        return 0
4
5    is_prime = [True] * n
6    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime by definition
7
8    i = 2
9    while i * i < n:  # composites with smallest prime factor > sqrt(n) are already handled
10        if is_prime[i]:
11            # start at i*i: multiples 2i, 3i, ..., (i-1)*i were already marked by smaller primes
12            for multiple in range(i * i, n, i):
13                is_prime[multiple] = False
14        i += 1
15
16    return sum(is_prime)  # True counts as 1, False as 0

Time: O(n log log n) — total elimination work sums the harmonic series over primes, which converges to log log n.
Space: O(n) — the boolean sieve stores one entry per integer below n.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n√n)	O(1)	Only when n is tiny (≤ 10,000) and allocating O(n) memory is forbidden
Sieve of Eratosthenes	O(n log log n)	O(n)	Standard answer for interview; handles n up to ~10^7 comfortably

Common Mistakes

Including n itself: using range(2, n + 1) or checking candidate <= n counts primes ≤ n instead of < n — the problem says strictly less than n, so n must be excluded.
Starting the inner sieve loop at i * 2 instead of i * i: every multiple k × i where k < i was already crossed off when the prime k was processed, so restarting at 2i re-marks the same slots and adds unnecessary work.
Missing the n ≤ 2 edge case: for n = 0 or n = 1, there are no valid candidates; without an early return, attempting to set is_prime[0] = is_prime[1] = False on a zero- or one-element array causes an index error.
In the brute force, checking divisors up to num - 1 instead of sqrt(num): if d > sqrt(num) divides num, then num / d < sqrt(num) is a smaller factor that would already have been caught — checking past the square root is pure wasted work and turns O(n√n) into O(n²).
Integer overflow on i * i in Java and C++: for large n, the product i * i can silently overflow a 32-bit int; casting to long / long long before the comparison ((long) i * i < n) prevents the outer loop from terminating too early.

Count Primes — Solution