Count Prime Numbers — Sieve of Eratosthenes
Implement countPrimes
You're handed a single non-negative integer
n. Your task: count how many primes live in the range below it — every prime p with p < n.
Checking each candidate's primality independently repeats the same work over and over — the Sieve of Eratosthenes instead crosses off composites in bulk: once a number i is confirmed prime, every multiple of i starting at i² is guaranteed composite and can be marked in one pass, with no divisor checks needed for any of them individually.
Example 1:
Input: n = 10
Output: 4
Example 2:
Input: n = 0
Output: 0
Example 3:
Input: n = 1
Output: 0
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ n ≤ 5 × 10⁶
n =
10