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