## Question

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`

## Algorithm

The basic thought is that you can use brute force to check each number less than n is a prime;

Or

You can utilize a smarter way: https://leetcode.com/problems/count-primes/solution/

Check out this solution explanation.

`j`

start from `i*I`

is because it doesn't have to start from 2 since all those numbers is less than j and may be calculated.

`j += I`

each time the number is skip by `I`

because we are checking the product of `i`

## Code

class Solution { public int countPrimes(int n) { if (n == 1 || n == 0) return 0; boolean[] memo = new boolean[n]; for (int i = 2; i <= (int) Math.sqrt(n); i++) { if (memo[i] == false) { for (int j = i*i; j < n; j += i) { memo[j] = true; } } } int res = 0; for (boolean m : memo) { if (!m) { res++; } } return res - 2; } }