LeetCode 204: Count Primes

A clear explanation of counting prime numbers less than n using the Sieve of Eratosthenes.

leetcodemathprimesieve

Problem Restatement

We are given an integer n.

We need to count how many prime numbers are strictly less than n.

A prime number is a number greater than 1 that has exactly two positive divisors:

  • 1
  • itself

The official statement says: given an integer n, return the number of prime numbers that are strictly less than n.

Input and Output

Item Meaning
Input Integer n
Output Number of primes less than n
Prime definition Number greater than 1 with exactly two divisors
Important detail Count numbers strictly less than n

Example function shape:

def countPrimes(n: int) -> int:
    ...

Examples

Example 1:

n = 10

Prime numbers less than 10 are:

2, 3, 5, 7

Count:

4

Example 2:

n = 0

There are no positive primes less than 0.

Answer:

0

Example 3:

n = 2

We count primes strictly less than 2.

There are none.

Answer:

0

First Thought: Check Every Number

The direct idea is:

  1. Try every number from 2 to n - 1.
  2. Check whether each number is prime.
  3. Count how many are prime.

To check whether a number x is prime:

  • Try dividing by every integer from 2 to sqrt(x).
  • If any divisor works, x is not prime.

Example:

x = 11

Check:

11 % 2 != 0
11 % 3 != 0

Since no divisor works, 11 is prime.

Problem With the Direct Method

Checking every number independently repeats a lot of work.

For example:

  • While checking 12, we mark it non-prime.
  • Later while checking 18, 24, 30, and many others, we repeat similar divisibility work.

This becomes slow for large n.

We need a method that removes many composite numbers efficiently.

Key Insight: Sieve of Eratosthenes

Instead of testing each number independently, we can eliminate composite numbers in batches.

Idea:

  • Start by assuming every number is prime.
  • Pick a prime number.
  • Mark all of its multiples as non-prime.
  • Repeat.

For example:

2, 3, 4, 5, 6, 7, 8, 9, 10

Start with 2.

All multiples of 2 greater than 2 are not prime:

4, 6, 8, 10

Next prime is 3.

Mark multiples of 3:

6, 9

Continue.

The remaining unmarked numbers are prime.

This algorithm is called the Sieve of Eratosthenes.

Why We Start From i * i

Suppose we are processing prime number i.

Example:

i = 5

Multiples:

5 * 2 = 10
5 * 3 = 15
5 * 4 = 20
5 * 5 = 25

The smaller multiples were already removed earlier:

  • 10 by 2
  • 15 by 3
  • 20 by 2

So we only need to start from:

i * i

This avoids redundant work.

Algorithm

  1. If n <= 2, return 0.
  2. Create a boolean array is_prime.
  3. Initially assume every number is prime.
  4. Mark 0 and 1 as non-prime.
  5. For each number i from 2 to sqrt(n):
    • If i is prime:
      • Mark all multiples starting from i * i as non-prime.
  6. Count how many values remain True.

Walkthrough

Use:

n = 10

Initial table:

Number Prime?
0 False
1 False
2 True
3 True
4 True
5 True
6 True
7 True
8 True
9 True

Process 2:

Mark:

4, 6, 8

as non-prime.

Process 3:

Mark:

9

as non-prime.

Final primes:

2, 3, 5, 7

Count:

4

Correctness

Initially, the algorithm assumes every integer greater than 1 is prime.

Whenever the algorithm processes a prime number p, it marks every multiple of p greater than or equal to p^2 as non-prime.

Every marked number is composite because it has at least two factors:

p × k

for some integer k >= p.

Now consider any composite number x.

Since x is composite, it has a prime factor p such that:

p <= sqrt(x)

When the algorithm processes p, it marks all multiples of p, including x, as non-prime.

Therefore every composite number is eventually removed.

Any number that remains unmarked cannot have any divisor greater than 1 and smaller than itself, so it must be prime.

Thus the algorithm counts exactly the prime numbers less than n.

Complexity

Metric Value Why
Time O(n log log n) Sieve marking process
Space O(n) Boolean array

The sieve is much faster than checking every number independently.

Implementation

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

        i = 2

        while i * i < n:
            if is_prime[i]:
                j = i * i

                while j < n:
                    is_prime[j] = False
                    j += i

            i += 1

        return sum(is_prime)

Code Explanation

Create the prime table:

is_prime = [True] * n

Initially every number is assumed prime.

Mark 0 and 1:

is_prime[0] = False
is_prime[1] = False

The outer loop processes candidate primes:

while i * i < n:

We only need to process up to sqrt(n).

If i is still prime:

if is_prime[i]:

start marking multiples:

j = i * i

Continue marking:

is_prime[j] = False
j += i

Finally count all remaining prime entries:

return sum(is_prime)

In Python, True behaves like 1, so summing the boolean list counts primes.

Optimized Python Version

Python slicing can mark multiples more compactly:

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

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

        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                is_prime[i * i:n:i] = [False] * len(range(i * i, n, i))

        return sum(is_prime)

The earlier version is usually easier to understand during interviews.

Testing

def run_tests():
    s = Solution()

    assert s.countPrimes(10) == 4
    assert s.countPrimes(0) == 0
    assert s.countPrimes(1) == 0
    assert s.countPrimes(2) == 0
    assert s.countPrimes(3) == 1
    assert s.countPrimes(100) == 25

    print("all tests passed")

run_tests()
Test Why
10 Standard example
0 Small boundary
1 No primes
2 Strictly less than 2
3 Smallest nonzero answer
100 Larger correctness check