题目

难度：★★☆☆☆
类型：数学

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

示例

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

解答

方案1：暴力求解

写一个判断输入数字是否是质数的函数（is_prime），并对输入范围内的所有数字进行判断，统计是质数的数量。

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        def is_prime(x):
            """
            判断质数
            :param x:
            :return:
            """
            if x <= 1:
                return False
            for i in range(2, int(x**0.5)+1):
                if x % i == 0:
                    return False
            return True

        return sum([is_prime(x) for x in range(2, n)])

不过这个办法提交会超时。

方案2：厄拉多塞筛法

西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，质数的因子除了1就是它本身，因此从2开始的任意一个数x，x乘一个大于1的正整数得到的数字一定不是质数，根据这个原理，我们可以进行如下操作：

1. 要寻找到正整数n为止的质数个数，构造一个长度为n的向量output，output[i]表示正整数i是否是质数，初始化这个向量中所有的元素为1（True）。

2. output前两个数置零（1和2不是质数），遍历从2开始到suqare(n)+1范围内的所有正整数i，将output向量中所有是i的正整数倍（大于1）的数所在位置全部置零。

3. 循环结束后得到的output向量即可代表相应位置的每一个正整数是否为质数，求和即为结果。

class Solution(object):

    def countPrimes(self, n):

        if n <= 2:
            return 0

        output = [1] * n                                        # 首先生成一个全部为1的列表
        output[0], output[1] = 0, 0
        for i in range(2, int(n**0.5)+1):
            if output[i] == 1:                                  # 如果i为质数
                output[i*2:n:i] = [0] * len(output[i*2:n:i])    # 将i的倍数置为0
                print(i, output)
        return sum(output)（）

如有疑问或建议，欢迎评论区留言~