LeetCode 204: Count Primes Solution in Python Explained

Problem Statement

In LeetCode 204: Count Primes, you’re given:

• An integer n where 0 ≤ n ≤ 5 * 10⁶.
• Your task is to return the number of prime numbers strictly less than n.

For example, if n = 10, the primes are 2, 3, 5, 7, so the answer is 4. This differs from linked list problems like LeetCode 203: Remove Linked List Elements, focusing instead on number theory and optimization.

Constraints

• 0 ≤ n ≤ 5 * 10⁶.

Examples

Let’s see some cases:

Copy codeInput: n = 10
Output: 4
Explanation: Primes < 10 are 2, 3, 5, 7 (4 primes).

Copy codeInput: n = 0
Output: 0
Explanation: No primes less than 0.

Copy codeInput: n = 2
Output: 0
Explanation: No primes less than 2 (2 itself is not counted).

These examples clarify that we’re counting primes below n.

Understanding the Problem

How do we solve LeetCode 204: Count Primes in Python? For n = 10, we need to identify 2, 3, 5, 7. A naive approach might test each number up to n for primality, but that’s slow for large n. This isn’t a cycle detection problem like LeetCode 202: Happy Number; it’s about efficiently sieving out non-primes. We’ll use: 1. Sieve of Eratosthenes: O(n log log n) time, O(n) space—our best solution. 2. Trial Division: O(n * sqrt(n)) time, O(1) space—an alternative.

Let’s explore the best solution.

Best Solution: Sieve of Eratosthenes Approach

Explanation

The Sieve of Eratosthenes is a classic algorithm to find all primes up to n:

• Create a boolean array is_prime from 0 to n-1, initially all True.
• Set 0 and 1 to False (not prime).
• For each prime i, mark its multiples as False (not prime).
• Count the remaining True values.

It’s O(n log log n) time (highly efficient for large n) and O(n) space (array size), making it the best solution for this problem.

For n = 10, it marks out 4, 6, 8, 9, leaving 2, 3, 5, 7.

Step-by-Step Example

Example 1: n = 10

Goal: Return 4.

• Step 1: Initialize.
• is_prime = [True] * 10 (0 to 9).
• is_prime[0] = is_prime[1] = False.
• count = 0.
• Step 2: Sieve.
• i = 2: Prime, mark multiples:
• 4, 6, 8 → False.
• is_prime = [F, F, T, T, F, T, F, T, F, T].
• i = 3: Prime, mark multiples:
• 6, 9 → False (6 already False).
• is_prime = [F, F, T, T, F, T, F, T, F, F].
• i = 4: False, skip.
• i = 5: Prime, mark 10 (out of range), stop at sqrt(10) ≈ 3.
• Step 3: Count.
• is_prime[2:] = [T, T, F, T, F, T, F, F].
• Count True: 2, 3, 5, 7 → 4.
• Output: 4.

Example 2: n = 5

Goal: Return 3.

• Step 1: is_prime = [T, T, T, T, T], set 0, 1 to F.
• Step 2:
• i = 2: Mark 4 → F.
• i = 3: No multiples < 5.
• Step 3: [F, F, T, T, F], count 2, 3 → 3.
• Output: 3.

How the Code Works (Sieve of Eratosthenes) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef countPrimes(n: int) -> int:
    # Line 1: Handle edge cases
    if n <= 2:
        # No primes less than 2 (e.g., n = 0, 1, 2)
        return 0

    # Line 2: Initialize sieve array
    is_prime = [True] * n
    # Array of n Trues (e.g., [T, T, T, T, T] for n=5)
    is_prime[0] = is_prime[1] = False
    # 0 and 1 are not prime (e.g., [F, F, T, T, T])

    # Line 3: Mark non-primes using sieve
    for i in range(2, int(n ** 0.5) + 1):
        # Up to sqrt(n) (e.g., i = 2, 3 for n=10)
        if is_prime[i]:
            # If i is prime (e.g., i = 2)
            for j in range(i * i, n, i):
                # Mark multiples (e.g., 4, 6, 8)
                is_prime[j] = False
                # Set to False (e.g., is_prime[4] = F)

    # Line 4: Count primes
    return sum(is_prime)
    # Sum Trues (e.g., [F, F, T, T, F, T, F, T, F, F] → 4)

This solution is both elegant and optimized.

Alternative: Trial Division Approach

Explanation

The Trial Division approach checks each number for primality:

• For each i from 2 to n-1, test if it’s prime by checking divisors up to sqrt(i).
• Increment a counter for each prime found.

It’s O(n * sqrt(n)) time (slow for large n) and O(1) space, making it a simple but less efficient alternative.

Step-by-Step Example

For n = 10:

• 2: Prime (no divisors), count = 1.
• 3: Prime, count = 2.
• 4: Divisible by 2, skip.
• 5: Prime, count = 3.
• 6, 8: Not prime.
• 7: Prime, count = 4.
• 9: Divisible by 3, skip.
• Output: 4.

How the Code Works (Trial Division)

Copy codedef countPrimesTrial(n: int) -> int:
    def is_prime(num):
        if num < 2:
            return False
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

    count = 0
    for i in range(2, n):
        if is_prime(i):
            count += 1
    return count

Complexity

• Sieve of Eratosthenes:
• Time: O(n log log n) – efficient sieving.
• Space: O(n) – array size.
• Trial Division:
• Time: O(n * sqrt(n)) – checks each number.
• Space: O(1) – no extra space.

Efficiency Notes

Sieve of Eratosthenes is our best solution with near-linear time and scalability. Trial Division is intuitive but impractical for large n.

Key Insights

• Sieve: Eliminates multiples efficiently.
• Prime: Only 2 factors.
• Optimization: Sqrt bound.

Additional Example

For n = 15:

• Sieve: 2, 3, 5, 7, 11, 13 → 6.
• Trial: Same result, slower.

Edge Cases

• n = 0, 1, 2: 0 (no primes).
• n = 3: 1 (just 2).

Both handle these well.

Final Thoughts

LeetCode 204: Count Primes in Python is a fantastic dive into prime numbers. Sieve of Eratosthenes shines with efficiency, while Trial Division offers simplicity. Want more? Try LeetCode 263: Ugly Number or LeetCode 191: Number of 1 Bits. Test your skills—Solve LeetCode 204 on LeetCode with n = 10 (expecting 4)—count those primes today!