Given an integer n, return the number of prime numbers that are strictly less than n.A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.For example, 2, 3, 5, 7 are prime numbers, but 4, 6, 8, 9 are not.### Constraints* 0 <= n <= 5 * 10^6### ExampleInput: n = 10Output: 4Explanation: There are 4 prime numbers less than 10: 2, 3, 5, 7.
Solution
Approach: Sieve of EratosthenesTo efficiently count primes up to n, we can use the Sieve of Eratosthenes algorithm. This method marks multiples of each prime number as not prime, starting from the smallest prime.Here's the breakdown:* Initialization: Create a boolean array, is_prime, of size n, and initialize all entries to true. This array will keep track of whether a number is prime or not. We know 0 and 1 are not prime, so set is_prime[0] and is_prime[1] to false.* Sieving Process: Iterate from p = 2 up to sqrt(n) (inclusive). This optimization works because if a number k is composite, it must have at least one prime factor less than or equal to sqrt(k).* Marking Multiples: If is_prime[p] is true, it means p is a prime number. Then, mark all multiples of p as not prime. Start marking from p*p because any smaller multiples (e.g., 2*p, 3*p, etc.) would have already been marked by smaller prime factors.* Counting Primes: After the sieving process is complete, iterate through the is_prime array from 2 up to n-1. Count all indices i where is_prime[i] is true. This count will be the total number of primes less than n.### Python Solutionpythonclass Solution: def countPrimes(self, n: int) -> int: if n <= 2: return 0 # Initialize a boolean array 'is_prime' and set all entries to true # Numbers 0 and 1 are not prime is_prime = [True] * n is_prime[0] = False is_prime[1] = False # Iterate from 2 up to sqrt(n) # Numbers are marked false starting from p*p because smaller multiples # would have already been marked by smaller primes. for p in range(2, int(n**0.5) + 1): if is_prime[p]: # Mark multiples of p as not prime for multiple in range(p*p, n, p): is_prime[multiple] = False # Count primes count = 0 for i in range(2, n): if is_prime[i]: count += 1 return count
