Count Primes

Sqrt(x)

Pascal's Triangle

Count how many prime numbers are strictly less than a given non-negative integer n.

Given a non-negative integer `n`, return the number of prime numbers that are **strictly less than** `n`.

A prime is a whole number greater than `1` whose only positive divisors are `1` and itself.

**Input / output**
- Input: `n: integer`
- Output: the count of primes below `n`

**Examples**
1. `n = 10` returns `4` (the primes `2, 3, 5, 7`).
2. `n = 0` returns `0`.
3. `n = 2` returns `0` (no primes are below `2`).

**Constraints**
- `0 <= n <= 5,000,000`

**Follow-up**
A trial-division scan is `O(n * sqrt(n))`. Can you reach `O(n log log n)` with the Sieve of Eratosthenes, and why is it safe to start crossing out multiples of `p` at `p * p`?

- We need every prime below `n`, not including `n` itself.
- Checking each number independently repeats a lot of work.
- A sieve marks composite numbers once and counts what remains.

Understand the Pattern

- If `n` is `0`, `1`, or `2`, there are no primes below it.
- Return `0` immediately for those inputs.
- This also lets the sieve assume `n >= 3`.

Handle the Tiny Cases

- Assume every number from `2` to `n-1` is prime.
- For each prime `p`, cross out its multiples starting at `p * p`.
- Anything still marked prime at the end is counted.

Sieve of Eratosthenes

- Starting at `p * p` is safe because smaller multiples were already crossed out by smaller primes.
- Time complexity is `O(n log log n)`.
- Space complexity is `O(n)` for the boolean sieve.