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

Example 1:

<strong>Input:</strong> n = 10
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 primes less than 10: 2, 3, 5, 7.

Example 2:

<strong>Input:</strong> n = 0
<strong>Output:</strong> 0

Example 3:

<strong>Input:</strong> n = 1
<strong>Output:</strong> 0

Constraints:

• 0 <= n <= 5 * 10<sup>6</sup>

Naïve Approach (Time Limit Exceeded)

class PrimeValidator:
   def count_below_bound(self, bound: int) -> int:
       total_primes = 0
       for candidate in range(2, bound):
           divisor_limit = int(candidate ** 0.5)
           is_prime_number = True
           for factor in range(2, divisor_limit + 1):
               if candidate % factor == 0:
                   is_prime_number = False
                   break
           if is_prime_number:
               total_primes += 1
       return total_primes

Optimized: Sieve of Eratosthenes

import math

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

       prime_status = [True] * limit
       prime_status[0] = prime_status[1] = False

       for base in range(2, int(math.sqrt(limit)) + 1):
           if prime_status[base]:
               for multiple in range(base * base, limit, base):
                   prime_status[multiple] = False

       return sum(prime_status)

The core improvement comes from the Sieve of Eratosthenes:

To find all primes below a natural number n, you only need to filter out the multiples of every prime that is no greater than √n. What remains are the primes.

Algorithm Overview

1. Begin with 2, and mark all multiples of each prime as composite.
2. Repeat this process until all numbers up to √n have been processed.

Step-by-Step

1. Initialization:
   • Create a boolean list prime_status of length n, initially all True. prime_status[i] indicates whether i is prime.
   • Set prime_status[0] and prime_status[1] to False since 0 and 1 are not prime.
2. Mark composites:
   • Iterate starting from 2. For each unmarked number base, mark all its multiples (starting from base * base) as composite.
   • Starting at base * base avoids redundant work because smaller multiples have already been handled by earlier primes.
3. Optimization:
   • The loop stops when base > √n, because any larger prime’s multiples would exceed n or would have already been covered.

Why start from base * base?

When processing a prime base, every composite of the form base * k with k < base has already been marked when we processed the smaller factors. For example, when base = 3, the multiples 6 and 9 were already handled by base = 2 and base = 3 respectively. Beginning at base * base skips this duplication.

Why stop at √n?

A composite number n can always be written as a * b. If both a and b were larger than √n, their product would exceed n. Thus, at least one factor must be ≤ √n, so it suffices to eliminate multiples of numbers up to √n.