We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Primes

Difficulty: Medium

Problem Description

Given an integer n, return the number of prime numbers that are strictly less than n.

Key Insights

  • A prime number is defined as a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
  • The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given limit, which can be used to solve this problem.
  • Edge cases include n values of 0 and 1, where there are no prime numbers.

Space and Time Complexity

Time Complexity: O(n log log n) - due to the Sieve of Eratosthenes. Space Complexity: O(n) - for the storage of the boolean array indicating prime status.

Solution

To solve the problem of counting prime numbers less than n, we can utilize the Sieve of Eratosthenes algorithm. This algorithm works by iteratively marking the multiples of each prime number starting from 2. The positions that remain marked as true in a boolean array indicate prime numbers. Once we complete the marking process, we can simply count the number of true values that represent prime numbers less than n.

Code Solutions

def countPrimes(n):
    if n < 2:
        return 0
    
    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]:
            for j in range(i * i, n, i):
                is_prime[j] = False
    
    return sum(is_prime)  # Count the number of True values in the array
← Back to All Questions