Domain 1EasyCORE

Count Primes

The problem asks us to count the number of prime numbers less than a given non-negative integer `n`. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The input is a single integer `n`, and the output should be an integer representing the count of prime numbers less than `n`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Math

204. Count Primes

Model: qwen2.5-coder:14b
Topics: Hash Table,Math
FAANG asked: 1
Acceptance rate: 32.3%


Problem Breakdown

The problem asks us to count the number of prime numbers less than a given non-negative integer n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The input is a single integer n, and the output should be an integer representing the count of prime numbers less than n.

Inputs:

  • An integer n (0 <= n <= 5 * 10^6)

Outputs:

  • An integer representing the count of prime numbers less than n

Implicit Constraints/Edge Cases:

  • If n is less than or equal to 2, there are no prime numbers less than n.
  • The upper limit for n is quite large (5 * 10^6), so the solution must be efficient in terms of both time and space.

Intuition

A brute-force approach would involve checking each number from 2 up to n-1 to see if it is prime. For each number, we would check divisibility by all numbers less than its square root. This approach is inefficient because it has a time complexity of O(n * sqrt(n)), which is not feasible for large values of n.

A more efficient approach is the Sieve of Eratosthenes algorithm. The key insight is to iteratively mark the multiples of each prime number starting from 2. By doing this, we can efficiently identify all non-prime numbers up to n. This reduces the time complexity to O(n log log n), which is much more efficient for large values of n.

Approach

  1. Initialization: Create a boolean array is_prime of size n, initialized to True. The index represents the number, and the value at that index indicates whether the number is prime.
  2. Mark Non-Primes: Iterate over each number starting from 2. For each prime number found, mark all its multiples as non-prime by setting the corresponding indices in the is_prime array to False.
  3. Count Primes: After processing all numbers up to the square root of n, count the number of True values in the is_prime array (excluding index 0 and 1, since they are not prime).

Complexity Analysis

  • Time Complexity: O(n log log n) - This is due to the fact that each number is marked as non-prime a logarithmic number of times.
  • Space Complexity: O(n) - We use an array of size n to keep track of prime status for each number.

Solution

def countPrimes(n):
    if n <= 2:
        return 0
    
    # Initialize a boolean array to mark prime numbers
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime numbers
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            # Mark all multiples of i as non-prime
            for j in range(i*i, n, i):
                is_prime[j] = False
    
    # Count the number of primes
    return sum(is_prime)

# Example usage:
print(countPrimes(10))  # Output: 4

Edge Cases Handled

  • n = 0: The function returns 0 because there are no prime numbers less than 0.
  • n = 1: The function returns 0 because there are no prime numbers less than 1.
  • n = 2: The function returns 0 because there are no prime numbers less than 2.
  • Large n (e.g., 5 * 10^6): The Sieve of Eratosthenes efficiently handles large values of n within the given constraints.