Code Implementation

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        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)
      

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;
        std::vector<bool> is_prime(n, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i * i < n; ++i) {
            if (is_prime[i]) {
                for (int j = i * i; j < n; j += i) {
                    is_prime[j] = false;
                }
            }
        }
        return std::count(is_prime.begin(), is_prime.end(), true);
    }
};
      

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) count++;
        }
        return count;
    }
}
      

var countPrimes = function(n) {
    if (n <= 2) return 0;
    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime.reduce((acc, val) => acc + (val ? 1 : 0), 0);
};
      

Problem Description

The "Count Primes" problem asks you to determine the number of prime numbers that are less than a given non-negative integer n. A prime number is defined as a number greater than 1 that has no positive divisors other than 1 and itself.

• Input: A single integer n.
• Output: The count of prime numbers strictly less than n.
• Constraints: 0 ≤ n ≤ 5 * 10^6.

For example, if n = 10, the primes less than 10 are 2, 3, 5, and 7, so the output should be 4.

Thought Process

At first glance, you might think to check each number less than n to see if it is prime. For each number, you could try dividing it by every integer less than itself to see if it is only divisible by 1 and itself. However, this would be very slow, especially for large values of n.

To optimize, recall that a number is not prime if it can be divided by any number less than or equal to its square root. But even this optimization, applied to every number below n, is not fast enough for large n.

Instead, we can use a classic algorithm called the Sieve of Eratosthenes. This method systematically marks the multiples of each prime number as not prime, ensuring that every number is checked in an efficient way.

The key shift is from checking each number for primality ("brute force") to eliminating non-primes in a batch process, which is much faster.

Solution Approach

We use the Sieve of Eratosthenes algorithm to efficiently count the number of primes less than n. Here’s how the algorithm works, step by step:

1. Initialize a Boolean List:
   • Create a list (or array) called is_prime of length n, where each element is initially set to True.
   • Set is_prime[0] and is_prime[1] to False because 0 and 1 are not prime.
2. Eliminate Non-Primes:
   • Iterate from 2 up to sqrt(n) (since any composite number less than n must have a factor less than or equal to its square root).
   • For each number i that is still marked as True (i.e., prime), mark all multiples of i (starting from i * i) as False (not prime).
3. Count Primes:
   • After the sieve, count how many entries in is_prime are still True. This is the number of primes less than n.

The Sieve of Eratosthenes is efficient because each composite number is marked only once, and we avoid redundant work by starting at i * i for each prime.

Example Walkthrough

Let’s walk through the algorithm with n = 10:

1. Initialize:
   • is_prime = [False, False, True, True, True, True, True, True, True, True]
2. First iteration (i = 2):
   • 2 is prime, so mark multiples of 2 (i.e., 4, 6, 8) as not prime:
   • is_prime = [False, False, True, True, False, True, False, True, False, True]
3. Second iteration (i = 3):
   • 3 is prime, so mark multiples of 3 (i.e., 6, 9) as not prime (6 already marked):
   • is_prime = [False, False, True, True, False, True, False, True, False, False]
4. i = 4:
   • 4 is already marked as not prime, so skip.
5. Count:
   • Primes less than 10 are at indices 2, 3, 5, 7 (all True), so the answer is 4.

Time and Space Complexity

• Brute-force approach:
  • For each number less than n, check for primality up to its square root.
  • Time Complexity: O(n√n) — too slow for large n.
  • Space Complexity: O(1) — only a few variables needed.
• Sieve of Eratosthenes:
  • Time Complexity: O(n log log n) — very efficient for large n.
  • Space Complexity: O(n) — we store an array of size n to keep track of primes.

The sieve is much more efficient for the problem constraints, allowing us to handle very large values of n.

Summary

The "Count Primes" problem is a classic example where a brute-force approach is too slow, but an optimized algorithm—the Sieve of Eratosthenes—solves it efficiently. By marking multiples of each found prime, we quickly eliminate non-primes and count the remaining True values. This method is both time- and space-efficient, and is a great tool for anyone working with prime numbers in programming.