# Leetcode 204. Count Primes

May 10, 2021

[easy]

Count the number of prime numbers less than a non-negative number, `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`

**[Think]**

- create a boolean array and default them as true
- change them to false if there you can multiple them

**[Trick]**

- if already change to false, don’t need to change and scan again
- for (int j = i*i; j < n; j+= i)

**[Second]**

- use notPrime