题目链接：
思路：
首先要知道如何判断一个数字是否为素数。具体方法可以看其次，如果朴素的判断，那么会因为效率底下而超时。
所以在我们每次找到素数的时候，可以把素数的倍数都标记为非素数。这样可以节省轮询的时间。算法复杂度：
时间：O(nloglogn) (time complexity for Sieve of Eratosthenes Algorithm)空间：O(n)
代码：
class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ if n < 3: return 0 primes = [True] * n primes[0] = primes[1] = False for i in range(2, int(n**0.5)+1): if primes[i]: for j in range(i*i, n, i): primes[j] = False return sum(primes)