Count Primes

How it works

Instead of checking each number for primality, we can use the Sieve of Eratosthenes to efficiently mark composite numbers. The key insight is that when we find a prime number, all of its multiples must be composite. By marking these multiples, we eliminate the need to check them later. We start marking from the square of each prime because smaller multiples would have already been marked by smaller primes.

Steps

1. Create a boolean array sieve of size n, initialized to false (all numbers assumed prime).
2. Initialize a counter res to 0.
3. For each number from 2 to n-1:
   • If the number is not marked as composite (sieve[num] is false):
     • Increment the prime counter.
     • Mark all multiples of this number starting from num*num as composite.
4. Return the count of primes.

Complexity

• Time complexity: O(n log (log n))
• Space complexity: O(n)

Things to watch for

Including n in the Count

The problem asks for primes strictly less than n, not less than or equal to. Using range(2, n + 1) or i <= n will include n itself if it's prime.

Integer Overflow When Computing num * num

When starting the sieve from i * i, this multiplication can overflow for large values. Use long or cast before multiplying.

Forgetting to Handle n < 2

There are no primes less than 2. Failing to handle edge cases like n = 0, n = 1, or n = 2 can cause array index errors or incorrect results.

class Solution:
    def countPrimes(self, n: int) -> int:
        sieve = [False] * n
        res = 0
        for num in range(2, n):
            if not sieve[num]:
                res += 1
                for i in range(num * num, n, num):
                    sieve[i] = True
        return res

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> sieve(n, false);
        int res = 0;
        for (int num = 2; num < n; num++) {
            if (!sieve[num]) {
                res++;
                for (long long i = 1LL * num * num; i < n; i += num) {
                    sieve[i] = true;
                }
            }
        }
        return res;
    }
};