204. Count Primes

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

就是寻找比n小的素数有多少个

这里我们用了素数筛的方法，将时间复杂度降到线性时间，素数筛基本思想就是一个素数的倍数一定不是素数

https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95#Python_3.6

易懂版本：

class Solution:
    def countPrimes(self, n: int) -> int:
        ispri=[0,0]+[1]*(n-2)
        if n==0 or n==1:
            return 0
        for i in range(2,int(n**0.5)+1):
            if ispri[i]:
                for j in range(i*i,n,i):
                    ispri[j]=0
        return sum(ispri)
                

巧用list运算符,结果稍许提高了一些运算时间

    def countPrimes(self, n: int) -> int:
        ispri=[0,0]+[1]*(n-2)
        if n==0 or n==1:
            return 0
        for i in range(2,int(n**0.5)+1):
            if ispri[i]:
                ispri[i**2::i]=[0]*(len(ispri[i**2::i]))
        return sum(ispri)