```
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n<2:
return 0
is_prime = [True] * n
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(n ** 0.5)+1):
if is_prime[i]:
is_prime[i*i: n: i] = [False] * len(is_prime[i*i: n: i])
return sum(is_prime)
```

Sieve of Eratosthenes

see: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes