筛数法
1、从2向后遍历，每遇到一个数字，将其倍数所对应的 is_prime 设为False，
因此遇到新的数字num,is_prime[num]=True说明它不是任何2..num-1的数字的倍数，即质数。
def countPrimes(n): is_prime = [True]*(n+1) ans = 0 for num in range(2,n+1): if is_prime[num]: ans+=1 for k in range(1,n//num+1): is_prime[num*k]=False return ans
原文：https://www.cnblogs.com/zhaojiayu/p/14799884.html