## Description

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

Count the number of prime numbers less than a non-negative number, ** n**.

**Example:**

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

## Explanation

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

## Python Solution

```
class Solution:
def countPrimes(self, n: int) -> int:
is_primes = self.get_is_primes(n)
count = 0
for i in range(2, n):
if is_primes[i]:
count += 1
return count
def get_is_primes(self, number):
is_primes = [True for i in range(0, number + 1)]
for i in range(2, number):
if is_primes[i] == False:
continue
j = 2
while i * j <= number:
is_primes[i * j] = False
j += 1
return is_primes
```

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

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