# LeetCode 204: Count Primes

## Problem Restatement

We are given an integer `n`.

We need to count how many prime numbers are strictly less than `n`.

A prime number is a number greater than `1` that has exactly two positive divisors:

- `1`
- itself

The official statement says: given an integer `n`, return the number of prime numbers that are strictly less than `n`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of primes less than `n` |
| Prime definition | Number greater than `1` with exactly two divisors |
| Important detail | Count numbers strictly less than `n` |

Example function shape:

```python
def countPrimes(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 10
```

Prime numbers less than `10` are:

```text
2, 3, 5, 7
```

Count:

```python
4
```

Example 2:

```python
n = 0
```

There are no positive primes less than `0`.

Answer:

```python
0
```

Example 3:

```python
n = 2
```

We count primes strictly less than `2`.

There are none.

Answer:

```python
0
```

## First Thought: Check Every Number

The direct idea is:

1. Try every number from `2` to `n - 1`.
2. Check whether each number is prime.
3. Count how many are prime.

To check whether a number `x` is prime:

- Try dividing by every integer from `2` to `sqrt(x)`.
- If any divisor works, `x` is not prime.

Example:

```python
x = 11
```

Check:

```text
11 % 2 != 0
11 % 3 != 0
```

Since no divisor works, `11` is prime.

## Problem With the Direct Method

Checking every number independently repeats a lot of work.

For example:

- While checking `12`, we mark it non-prime.
- Later while checking `18`, `24`, `30`, and many others, we repeat similar divisibility work.

This becomes slow for large `n`.

We need a method that removes many composite numbers efficiently.

## Key Insight: Sieve of Eratosthenes

Instead of testing each number independently, we can eliminate composite numbers in batches.

Idea:

- Start by assuming every number is prime.
- Pick a prime number.
- Mark all of its multiples as non-prime.
- Repeat.

For example:

```text
2, 3, 4, 5, 6, 7, 8, 9, 10
```

Start with `2`.

All multiples of `2` greater than `2` are not prime:

```text
4, 6, 8, 10
```

Next prime is `3`.

Mark multiples of `3`:

```text
6, 9
```

Continue.

The remaining unmarked numbers are prime.

This algorithm is called the Sieve of Eratosthenes.

## Why We Start From `i * i`

Suppose we are processing prime number `i`.

Example:

```python
i = 5
```

Multiples:

```text
5 * 2 = 10
5 * 3 = 15
5 * 4 = 20
5 * 5 = 25
```

The smaller multiples were already removed earlier:

- `10` by `2`
- `15` by `3`
- `20` by `2`

So we only need to start from:

```python
i * i
```

This avoids redundant work.

## Algorithm

1. If `n <= 2`, return `0`.
2. Create a boolean array `is_prime`.
3. Initially assume every number is prime.
4. Mark `0` and `1` as non-prime.
5. For each number `i` from `2` to `sqrt(n)`:
   - If `i` is prime:
     - Mark all multiples starting from `i * i` as non-prime.
6. Count how many values remain `True`.

## Walkthrough

Use:

```python
n = 10
```

Initial table:

| Number | Prime? |
|---|---|
| 0 | False |
| 1 | False |
| 2 | True |
| 3 | True |
| 4 | True |
| 5 | True |
| 6 | True |
| 7 | True |
| 8 | True |
| 9 | True |

Process `2`:

Mark:

```text
4, 6, 8
```

as non-prime.

Process `3`:

Mark:

```text
9
```

as non-prime.

Final primes:

```text
2, 3, 5, 7
```

Count:

```python
4
```

## Correctness

Initially, the algorithm assumes every integer greater than `1` is prime.

Whenever the algorithm processes a prime number `p`, it marks every multiple of `p` greater than or equal to `p^2` as non-prime.

Every marked number is composite because it has at least two factors:

```text
p × k
```

for some integer `k >= p`.

Now consider any composite number `x`.

Since `x` is composite, it has a prime factor `p` such that:

```text
p <= sqrt(x)
```

When the algorithm processes `p`, it marks all multiples of `p`, including `x`, as non-prime.

Therefore every composite number is eventually removed.

Any number that remains unmarked cannot have any divisor greater than `1` and smaller than itself, so it must be prime.

Thus the algorithm counts exactly the prime numbers less than `n`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log log n)` | Sieve marking process |
| Space | `O(n)` | Boolean array |

The sieve is much faster than checking every number independently.

## Implementation

```python
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0

        is_prime = [True] * n

        is_prime[0] = False
        is_prime[1] = False

        i = 2

        while i * i < n:
            if is_prime[i]:
                j = i * i

                while j < n:
                    is_prime[j] = False
                    j += i

            i += 1

        return sum(is_prime)
```

## Code Explanation

Create the prime table:

```python
is_prime = [True] * n
```

Initially every number is assumed prime.

Mark `0` and `1`:

```python
is_prime[0] = False
is_prime[1] = False
```

The outer loop processes candidate primes:

```python
while i * i < n:
```

We only need to process up to `sqrt(n)`.

If `i` is still prime:

```python
if is_prime[i]:
```

start marking multiples:

```python
j = i * i
```

Continue marking:

```python
is_prime[j] = False
j += i
```

Finally count all remaining prime entries:

```python
return sum(is_prime)
```

In Python, `True` behaves like `1`, so summing the boolean list counts primes.

## Optimized Python Version

Python slicing can mark multiples more compactly:

```python
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0

        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False

        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                is_prime[i * i:n:i] = [False] * len(range(i * i, n, i))

        return sum(is_prime)
```

The earlier version is usually easier to understand during interviews.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.countPrimes(10) == 4
    assert s.countPrimes(0) == 0
    assert s.countPrimes(1) == 0
    assert s.countPrimes(2) == 0
    assert s.countPrimes(3) == 1
    assert s.countPrimes(100) == 25

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `10` | Standard example |
| `0` | Small boundary |
| `1` | No primes |
| `2` | Strictly less than `2` |
| `3` | Smallest nonzero answer |
| `100` | Larger correctness check |