# 0204. Count Primes

<https://leetcode.com/problems/count-primes>

## Description

Given an integer `n`, return *the number of prime numbers that are strictly less than* `n`.

**Example 1:**

```
**Input:** n = 10
**Output:** 4
**Explanation:** There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
```

**Example 2:**

```
**Input:** n = 0
**Output:** 0
```

**Example 3:**

```
**Input:** n = 1
**Output:** 0
```

**Constraints:**

* `0 <= n <= 5 * 106`

## ac1: simple

it's all about math

```java
class Solution {
    public int countPrimes(int n) {
        // edge cases
        if (n <= 2) return 0;

        List<Integer> list = new ArrayList<Integer>();
        list.add(2);

        for (int i = 3; i < n; i++) {
            if (isPrime(i, list)) list.add(i);
        }

        return list.size();
    }
    private boolean isPrime(int n, List<Integer> list) {
        double sqrt = Math.sqrt(n);
        for (int i = 0; i < list.size(); i++) {
            int curr = list.get(i);
            if (curr > sqrt) break;  // greater than square root, no need to check
            if (n % curr == 0) return false;
        }
        return true;
    }
}

// 2 3 5 7 9 11 13 17 19 23 29 ...   1 is not prime number
```