Count Primes - Leetcode Solution

The Count Primes problem on LeetCode asks us to count the number of prime numbers less than a given non-negative integer n.

To solve this problem, we can use the Sieve of Eratosthenes algorithm, which is an efficient algorithm for finding all prime numbers up to a given limit. The algorithm works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.

Here is the detailed solution in Python:

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        
        # initialize a boolean array to mark all numbers as potential prime
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        
        # iterate over the numbers up to the square root of n
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                # mark the multiples of i as composite
                for j in range(i * i, n, i):
                    is_prime[j] = False
        
        # count the number of primes
        return sum(is_prime)

We start by checking if n is less than or equal to 2, in which case there are no primes less than n. Otherwise, we initialize a boolean array is_prime of length n, where is_prime[i] represents whether i is prime or not. We then mark 0 and 1 as not prime, since they are not considered to be prime.

Next, we iterate over the numbers up to the square root of n, since any composite number less than n must have a prime factor less than or equal to its square root. For each prime number i, we mark its multiples as composite by iterating over all multiples i * j less than n and setting is_prime[i * j] to False. Note that we start marking the multiples of i from i * i, since any multiple less than i * i would have already been marked by a smaller prime factor.

Finally, we count the number of primes by summing the values in the is_prime array that are True.

The time complexity of this solution is O(n * log(log(n))), which is the time it takes to perform the Sieve of Eratosthenes algorithm. The space complexity is O(n) for the is_prime array.

1