algoadvance

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

Clarifying Questions

  1. Input Range: What is the expected range of the input n?
    • Generally, 1 <= n <= 5 * 10^6 based on typical constraints.
  2. Edge Case Checks:
    • What should be the result if n <= 2?
      • Since there are no primes less than 2, it should return 0 for n <= 2.
  3. Performance:
    • Is there a strict performance requirement?
      • Yes, solutions that iterate and check each number individually will be too slow for large n.

Strategy

To count prime numbers less than n, an efficient algorithm is needed: the Sieve of Eratosthenes.

Sieve of Eratosthenes Algorithm:

  1. Create a boolean array is_prime of size n and initialize all entries to True. This array indicates whether each number is a prime.
  2. Set is_prime[0] and is_prime[1] to False since 0 and 1 are not primes.
  3. For each integer p starting from 2, if p is a prime, mark all multiples of p as False (not prime).
  4. Continue the process until p^2 >= n.
  5. The count of True values in is_prime array will give the count of prime numbers less than n.

Code

def countPrimes(n: int) -> int:
    if n <= 2:
        return 0

    # Initialize a list to track prime numbers
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime numbers

    # Apply Sieve of Eratosthenes
    p = 2
    while p * p < n:
        if is_prime[p]:
            # Mark all multiples of p as False
            for multiple in range(p * p, n, p):
                is_prime[multiple] = False
        p += 1

    # Count all prime numbers
    return sum(is_prime)

# Example usage:
n = 10
print(countPrimes(n))  # Output is 4 (primes: 2, 3, 5, 7)

Time Complexity

This algorithm efficiently counts the number of primes less than a given number n in an optimal manner for large inputs.

Try our interview co-pilot at AlgoAdvance.com