题目
难度：★★☆☆☆
类型：数学
统计所有小于非负整数 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的正整数得到的数字一定不是质数，根据这个原理，我们可以进行如下操作：
要寻找到正整数n为止的质数个数，构造一个长度为n的向量output，output[i]表示正整数i是否是质数，初始化这个向量中所有的元素为1（True）。
output前两个数置零（1和2不是质数），遍历从2开始到suqare(n)+1范围内的所有正整数i，将output向量中所有是i的正整数倍（大于1）的数所在位置全部置零。
循环结束后得到的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)（）
如有疑问或建议，欢迎评论区留言~
