Count Primes

## Problem 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. ## Examples **Example 1:** ``` Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10: 2, 3, 5, 7. ``` **Example 2:** ``` Input: n = 0 Output: 0 ``` **Example 3:** ``` Input: n = 1 Output: 0 ``` ## Hints - Use the **Sieve of Eratosthenes** for an efficient O(n log log n) solution. - Create a boolean array of size `n` initialized to `True`. - For each prime `p` starting from 2, mark all multiples of `p` (starting from `p*p`) as not prime. - Count the remaining `True` entries.