1. Brute Force

Intuition

The most straightforward way to count primes is to check each number individually. A number is prime if it has no divisors other than 1 and itself. We can optimize the divisibility check by only testing divisors up to the square root of the number, since if a number has a factor larger than its square root, it must also have a corresponding factor smaller than its square root.

Algorithm

1. Initialize a counter res to 0.
2. For each number from 2 to n-1:
   • Assume the number is prime.
   • Check if any number from 2 to the square root of the current number divides it evenly.
   • If a divisor is found, mark it as not prime.
   • If no divisor is found, increment the counter.
3. Return the count of primes.

class Solution:
    def countPrimes(self, n: int) -> int:
        res = 0
        for num in range(2, n):
            isPrime = True
            for i in range(2, int(num ** 0.5) + 1):
                if num % i == 0:
                    isPrime = False
                    break
            if isPrime:
                res += 1
        return res

Time & Space Complexity

• Time complexity: $O(n \sqrt {n})$
• Space complexity: $O(1)$

---

2. Sieve of Eratosthenes

Intuition

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.

Algorithm

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.

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

Time & Space Complexity

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

---

3. Sieve of Eratosthenes (Optimal)

Intuition

We can optimize the sieve by observing that 2 is the only even prime. Instead of processing all numbers, we start by assuming half the numbers (all odd numbers plus 2) are prime, then only sieve odd numbers starting from 3. When marking multiples, we skip even multiples since they are already excluded. This cuts the work roughly in half.

Algorithm

1. If n < 3, return 0 (no primes less than 2).
2. Initialize count to n/2 (assuming 2 and all odd numbers are prime).
3. Create a boolean array isPrime of size n.
4. For each odd number i from 3 up to sqrt(n):
   • If i is not marked as composite:
     • Mark all odd multiples of i starting from i*i as composite.
     • Decrement count for each newly marked composite.
5. Return the final count.

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0

        isPrime = [False] * n
        count = n // 2

        for i in range(3, int(n ** 0.5) + 1, 2):
            if not isPrime[i]:
                for j in range(i * i, n, 2 * i):
                    if not isPrime[j]:
                        isPrime[j] = True
                        count -= 1

        return count

Time & Space Complexity

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

---

Common Pitfalls

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.

# Wrong: includes n
for num in range(2, n + 1):
# Correct: excludes n
for num in range(2, n):

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.

// Overflow risk when i is large
for (int j = i * i; j < n; j += i)
// Safe: use long arithmetic
for (long j = (long) i * i; j < n; j += i)

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.