LeetCode 204 - Count Primes

Difficulty: 🟡 Medium
Topics: Array, Math, Enumeration, Number Theory

Solution

Problem Understanding

The problem asks us to count how many prime numbers exist that are strictly smaller than a given integer n.

A prime number is a positive integer greater than 1 that has exactly two divisors: 1 and itself. Examples of prime numbers include 2, 3, 5, 7, and 11. Numbers like 1, 4, 6, and 9 are not prime because they either have fewer than two divisors or more than two divisors.

The input is a single integer n, and the output should be the number of prime numbers in the range [0, n), meaning all integers starting from 0 up to but not including n.

For example, when n = 10, the prime numbers less than 10 are:

So the answer is 4.

The constraints are important:

0 <= n <= 5 * 10^6

This upper bound is very large. A solution that individually checks every number for primality using trial division would become too slow at this scale. We need an algorithm that efficiently identifies many primes at once.

Several edge cases immediately stand out:

n = 0, there are no numbers to check, so the answer is 0
n = 1, there are still no primes
n = 2, the range below 2 contains no primes
Very large values like 5,000,000 require an efficient algorithm both in runtime and memory usage

The problem guarantees that the input is a non-negative integer, so we do not need to handle invalid input types or negative numbers.

Approaches

Brute Force Approach

The most straightforward approach is to iterate through every number from 2 to n - 1 and determine whether each number is prime.

To check if a number is prime, we can attempt dividing it by every integer from 2 up to its square root. If any divisor evenly divides the number, then the number is not prime. Otherwise, it is prime.

This approach is correct because every composite number has at least one factor less than or equal to its square root. By checking divisibility up to that point, we can accurately determine primality.

However, this method becomes too slow for the given constraints. If we test every number individually, the total work grows approximately proportional to:

n * sqrt(n)

With n as large as 5,000,000, this becomes computationally expensive.

Optimal Approach, Sieve of Eratosthenes

The key insight is that instead of checking each number independently, we can eliminate composite numbers in bulk.

If a number is prime, then every multiple of that number must be composite. For example:

Multiples of 2 greater than 2 are not prime
Multiples of 3 greater than 3 are not prime
Multiples of 5 greater than 5 are not prime

The Sieve of Eratosthenes uses this observation efficiently.

We create a boolean array where each index represents whether the number is currently considered prime. Initially, we assume every number greater than or equal to 2 is prime. Then:

Start from 2
Mark all multiples of 2 as composite
Move to the next unmarked number, 3
Mark all multiples of 3
Continue this process

By the end, all remaining unmarked numbers are prime.

An additional optimization is important:

When processing a prime number p, we start marking from p * p, not 2 * p.

Why?

Because smaller multiples such as 2 * p, 3 * p, and so on were already marked when processing smaller primes.

This significantly reduces unnecessary work.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n√n)	O(1)	Checks every number independently for primality
Optimal	O(n log log n)	O(n)	Uses the Sieve of Eratosthenes to eliminate composites efficiently

Algorithm Walkthrough

Handle small edge cases immediately.

If n <= 2, return 0 because there are no prime numbers less than 2. 2. Create a boolean array named is_prime.

The array has length n. Each index represents a number.

Initially:

Assume every number is prime
Set all entries to True
Explicitly mark 0 and 1 as False because they are not prime

Start iterating from 2.

For each number current:

If is_prime[current] is True, then current is prime
We now eliminate all multiples of current

Begin marking multiples starting from current * current.

This optimization works because smaller multiples were already processed by smaller primes.

For example, when processing 5:

10 was already marked by 2
15 was already marked by 3
20 was already marked by 2

So the first new multiple that still needs marking is 25. 5. Mark every multiple as composite.

Iterate through:

current * current,
current * current + current,
current * current + 2 * current,
...

Set each corresponding entry in is_prime to False. 6. Continue until current * current >= n.

Once the square exceeds n, all composites have already been handled. 7. Count all remaining True values.

Every remaining True index corresponds to a prime number.

Why it works

The algorithm relies on a fundamental property of composite numbers:

Every composite number has at least one prime factor less than or equal to its square root.

When we process each prime number and mark all its multiples, every composite number eventually gets marked as non-prime. Prime numbers themselves are never marked because they have no smaller prime divisors.

Therefore, the numbers that remain marked as prime at the end are exactly the prime numbers less than n.

Python Solution

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

        is_prime = [True] * n
        is_prime[0] = False
        is_prime[1] = False

        current = 2

        while current * current < n:
            if is_prime[current]:
                multiple = current * current

                while multiple < n:
                    is_prime[multiple] = False
                    multiple += current

            current += 1

        return sum(is_prime)

The implementation begins by handling the smallest inputs. Any value less than or equal to 2 cannot contain a prime number smaller than itself.

Next, the is_prime array is initialized. Each position represents whether the corresponding number is currently believed to be prime.

The main loop continues while current * current < n. This condition is sufficient because any composite number larger than the square root would already have been marked by a smaller factor.

Inside the loop, we only process numbers that are still marked as prime. For each prime number, we mark all of its multiples as non-prime.

The marking process begins at current * current, which avoids redundant work and improves efficiency.

Finally, the algorithm returns the count of all True values in the array, since those correspond to prime numbers.

Go Solution

func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    isPrime := make([]bool, n)

    for i := 2; i < n; i++ {
        isPrime[i] = true
    }

    for current := 2; current*current < n; current++ {
        if isPrime[current] {
            for multiple := current * current; multiple < n; multiple += current {
                isPrime[multiple] = false
            }
        }
    }

    count := 0

    for i := 2; i < n; i++ {
        if isPrime[i] {
            count++
        }
    }

    return count
}

The Go implementation follows the same algorithmic structure as the Python version.

One small difference is slice initialization. In Go, boolean slices default to false, so we explicitly set indices from 2 onward to true.

The counting step is also performed manually using a loop because Go does not provide a built-in equivalent of Python's sum() for boolean values.

Integer overflow is not a concern here because the constraint limit is well within Go's integer range.

Worked Examples

Example 1

Input:

n = 10

Initial state:

Number	0	1	2	3	4	5	6	7	8	9
is_prime	F	F	T	T	T	T	T	T	T	T

Process 2:

Mark multiples of 2 starting from 4.

Marked	4	6	8

Updated state:

Number	0	1	2	3	4	5	6	7	8	9
is_prime	F	F	T	T	F	T	F	T	F	T

Process 3:

Mark multiples of 3 starting from 9.

Marked	9

Updated state:

Number	0	1	2	3	4	5	6	7	8	9
is_prime	F	F	T	T	F	T	F	T	F	F

Stop because 4 * 4 > 10.

Remaining primes:

2, 3, 5, 7

Answer:

Example 2

Input:

n = 0

Since n <= 2, the algorithm immediately returns:

No sieve array is needed.

Example 3

Input:

n = 1

Again, since n <= 2, the algorithm immediately returns:

There are no prime numbers less than 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log log n)	Each composite number is marked a limited number of times
Space	O(n)	The sieve array stores primality information for every number below `n`

The time complexity of the Sieve of Eratosthenes is better than checking every number individually. Although multiple nested loops exist, the total amount of work is surprisingly efficient because marking operations only occur for prime numbers.

The space complexity is linear because we maintain a boolean array of size n.

Test Cases

solution = Solution()

assert solution.countPrimes(0) == 0      # no numbers to evaluate
assert solution.countPrimes(1) == 0      # no primes below 1
assert solution.countPrimes(2) == 0      # no primes below 2
assert solution.countPrimes(3) == 1      # only prime is 2
assert solution.countPrimes(4) == 2      # primes are 2 and 3
assert solution.countPrimes(5) == 2      # primes are 2 and 3
assert solution.countPrimes(10) == 4     # primes are 2, 3, 5, 7
assert solution.countPrimes(20) == 8     # verifies multiple sieve passes
assert solution.countPrimes(100) == 25   # standard known prime count
assert solution.countPrimes(1000) == 168 # larger correctness test

Test	Why
`n = 0`	Verifies lower boundary handling
`n = 1`	Ensures non-prime handling for very small inputs
`n = 2`	Confirms exclusive upper bound behavior
`n = 3`	Smallest input containing a prime
`n = 4`	Tests simple composite elimination
`n = 5`	Verifies counting logic
`n = 10`	Matches provided example
`n = 20`	Tests multiple prime elimination rounds
`n = 100`	Validates correctness on larger range
`n = 1000`	Stress test for sieve implementation correctness

Edge Cases

Edge Case 1, `n <= 2`

This is the most important boundary condition. Since the problem asks for primes strictly less than n, there are no valid primes when n is 0, 1, or 2.

A common mistake is accidentally counting 2 itself when n = 2. The implementation avoids this by immediately returning 0 whenever n <= 2.

Edge Case 2, Starting Marking at `2 * current`

A naive sieve implementation may begin marking multiples from 2 * current. While this still produces correct results, it performs a large amount of redundant work.

For example, when processing 5, values like 10, 15, and 20 were already marked by smaller primes.

Starting from current * current avoids duplicate operations and is critical for achieving optimal performance.

Edge Case 3, Large Inputs Near `5 * 10^6`

For very large values of n, inefficient primality testing becomes too slow.

The sieve implementation handles large inputs efficiently because each composite number is marked only a limited number of times. The boolean array uses linear space, which is acceptable under the problem constraints.

This ensures the solution remains performant even near the maximum input size.

LeetCode 204 - Count Primes

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach, Sieve of Eratosthenes

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Edge Cases

Edge Case 1, n <= 2

Edge Case 2, Starting Marking at 2 * current

Edge Case 3, Large Inputs Near 5 * 10^6

Edge Case 1, `n <= 2`

Edge Case 2, Starting Marking at `2 * current`

Edge Case 3, Large Inputs Near `5 * 10^6`