Idea: if er are looking at 3, the 3*3=9, 3*4=12, 3*5=15, 3*6=18, ... will not be prime. So we set a trueTable, and "predict" all numbers that will not be prime, and set them to False.

Also we just need to check from 2 to n^(1/2.0) because all numbers bigger than n^(1/2.0) has been set to either False or True.

Finally, we count how many True we have in or trueTable

```
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 2: return 0
if n == 2: return 0
res = 1
trueTable = [True]*n
trueTable[0:2] = [False]*2
for i in range(2, int(n**0.5) + 1):
if trueTable[i] == True:
trueTable[i*2:n:i] = [False]*((n - 1 - i*2)/i + 1)
return sum(trueTable)
```