```
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
Primes=[2]
result=1
if n<=2:
return 0
if n==3:
return 1
for i in range(3,n):
for p in Primes:
if p*p>i:
Primes.append(i)
result += 1
break
elif i%p==0:
break
else:
Primes.append(i)
result+=1
return result
```