题目描述

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

我的解法——两层循环（未AC）

直接两层循环
不遍历2~m-1，只遍历2 ~ √m.因为如果m能被2 ~ m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。
时间复杂度O(n^1.5)，空间复杂度O(1)

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        for i in range(2,n):
            flag = True
            for j in range(2,int(math.sqrt(i)) + 1):
                if(i % j == 0):
                    flag = False
                    break
            if(flag):
                res += 1
        return res

最优解法——埃拉托斯特尼筛法

先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。
注意蛋疼的1和2

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 1是质数
        if(n <= 1):
            return 0
        if(n == 2):
            return 0
        mask = [1] * (n + 1)
        i = 2
        mask[0] = 0
        mask[1] = 0
        mask[n] = 0
        
        while(i * i <= n):
            if(mask[i] == 1):
                for j in range(2,int(n / i) + 1):
                    mask[i * j] = 0
            i += 1
        
        return sum(mask)