```
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2: return 0
if n == 3: return 1
# l is a list of discovered prime nums
# prime nums other than 2 are all odd
l = [3]
# only test odd nums
for i in range(3, n, 2):
# i is prime if it doesn't have prime factors upto sqrt(i)
# only test prime nums in l as factors
bound = int(i ** 0.5)
for j in l:
if i % j == 0:
break
if j > bound:
l.append(i)
break
# 2 is not in list l, so add it on
return len(l) + 1
```

I keep a list l to store discovered prime nums and test new number only on those in l and smaller than sqrt(i). I also explicitly skip even numbers larger than 2. This should be a better algorithm than that in hint, better than n ** 1.5. But it end up with Time Limit Exceeded. Any suggestions? Thanks.