```
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n == 4:
return 2
elif n == 3:
return 1
elif n < 3:
return 0
array = [False] * n
array[3 : n: 2] = [True] * len(array[3 : n: 2])
array[5: n: 3] = [True] * len(array[5: n: 3])
i = 1
temp = i * 6
while temp - 1 < int(n ** 0.5) + 1:
if array[temp - 2] is False:
array[(temp - 1) - 1 + (temp - 1): n: (temp - 1)] = [True] * len(array[(temp - 1) - 1 + (temp - 1): n: (temp - 1)])
if temp + 1 < n and array[temp] is False:
array[(temp) + temp + 1: n: temp + 1] = [True] * len(array[(temp) + temp + 1: n: temp + 1])
i += 1
temp = i * 6
return n - sum(array[:-1]) - 2
```