LeetCode Solutions Blog

Count Primes

Number: 204

Difficulty: Medium

Paid? No

Problem Description

Given an integer n, return the number of prime numbers that are strictly less than n. For example, when n = 10 there are 4 prime numbers less than 10: 2, 3, 5, and 7.

Key Insights

The problem can be efficiently solved using the Sieve of Eratosthenes.
Only numbers less than n are considered.
Iterating only up to the square root of n will mark all non-prime numbers effectively.
An auxiliary boolean array can represent whether each number is prime.

Space and Time Complexity

Time Complexity: O(n log log n)
Space Complexity: O(n)

Solution

The Sieve of Eratosthenes algorithm is used to solve this problem. We create a boolean array of size n where each index initially assumes the number is prime. We then mark 0 and 1 as non-prime. For each number p starting from 2 up to the square root of n, if p is still marked as prime, we mark all multiples of p (starting at p*p) as non-prime. Finally, the count of true values in the boolean array gives the number of primes less than n.

Code Solutions

def countPrimes(n):
    # If n is less than 2, there are no prime numbers
    if n < 2:
        return 0
    # Initialize a boolean array indicating prime status for each number
    is_prime = [True] * n
    # 0 and 1 are not prime numbers
    is_prime[0] = is_prime[1] = False
    # Iterate over each number up to the square root of n
    p = 2
    while p * p < n:
        if is_prime[p]:
            # Mark multiples of p starting from p*p as non-prime
            for i in range(p * p, n, p):
                is_prime[i] = False
        p += 1
    # Sum up the True values to get the total count of primes
    return sum(is_prime)

# Example usage:
print(countPrimes(10))  # Expected output: 4