1.题目

原题

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

例子

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

2.解析

这道题最简单的就是暴力求解，定义一个函数判断是不是质数，为了减少计算量，就遍历i到sqrt(n)就行了，但是提交leetcode会超时。
第二个方法，是一个数学家家提出来的。其实思路很简单，这个数时质数了，后边所有他的倍数肯定不是质数，这就好说了，首先定义个长度为n的数组，初始假设都是质数，然后0，1位置都置0，以后遍历，只要遇到质数就让后边他的倍数都不是质数，如此就简单求解了。

3.python代码

#暴力求解，提交超时
class Solution:
    def countPrimes(self, n):
        count = 0
        for i in range(1, n):
            if self.isPrime(i):
                count += 1
        return count
    def isPrime(self, n):
        if n <= 1:
            return False
        for i in range(1, n//2+1):
            if i > 1 and n % i == 0:
                return False
        return True
#简便方法
    def countPrimes(self, n):
        if n <= 2:
            return 0
        prime = [1] * (n-1)
        prime[0], prime[1] = 0, 0
        for i in range(2, int(n**(1/2))+1):
            if prime[i] == 1:
                prime[i*2:n:i] = [0] * len(prime[i*2:n:i])
        return sum(prime)