## Description

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

Given an integer `n`

, return *the number of prime numbers that are strictly less than* `n`

.

**Example 1:**

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

**Example 2:**

Input:n = 0Output:0

**Example 3:**

Input:n = 1Output:0

**Constraints:**

`0 <= n <= 5 * 10`

^{6}

## Explanation

pre-calculate all primes numbers less than or equal to the given number

## Python Solution

```
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
is_prime = [True for i in range(n)]
is_prime[0] = False
is_prime[1] = False
for i in range(2, n):
if is_prime[i]:
for j in range(2 * i, n, i):
is_prime[j] = False
return sum(is_prime)
```

- Time complexity: O(N^2).
- Space complexity: O(N).

## One Thought to “LeetCode 204. Count Primes”