```
class Solution:
# @param {integer} n
# @return {integer}
def countPrimes(self, n):
if n <= 2:
return 0
else:
primes = [0,0] + [1]*(n-2)
nsqrt = int((n-1)**(0.5))
for i in range(2,nsqrt+1):
if primes[i] == 1:
for j in range(i**2,n,i):
primes[j] = 0
return sum(primes)
```