204. Count Primes

我的方法超时了，代码如下：

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        if n <= 2:
            return count
        for i in range(3, n):
            for j in range(2, i - 1):
                if i % j == 0:
                    count += 1
                    break
        return n - count - 2
                

依然超时的办法，代码如下：

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        if n <= 2:
            return count
        res = []
        res.append(2)
        count = 1
        for i in range(3, n):
            j = 0 
            while j < len(res):
                if i % res[j] == 0:
                    break
                j += 1
            if j >= len(res):
                res.append(i)
                count += 1
        return count
                

传说的## 厄拉多塞筛法

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