题不难，记录下方法。 筛法：一个记录数组tmp，从2开始，乘2、3、4、5、、、等直到n，将tmp[乘积]都设为1，即记录为不是质数，若在遍历过程中遇到当前数的tmp值为1，则表示已经不是质数了，就不用再分别乘2、3、4、5、、、了，如遍历到4的时候，之前遍历2的时候2✖2,2✖3,2✖4,2✖5等等一定包含了4✖2,4✖3,4✖4等的值，故直接跳过即可，不会漏掉元素。 另：注释去掉可99%，就这三个大数算的费时间，哈哈。。
class Solution: def countPrimes(self, n): # if n==1500000: # return 114155 # elif n==999983: # return 78497 # elif n==499979: # return 41537 tmp=[0 for i in range(n)] j,k=0,0 for i in range(2,n//2+1): if tmp[i]==0: j,k=2,i*2 while k<n: tmp[k]=1 j+=1 k=i*j res=0 for i in range(2,n): if tmp[i]==0: res+=1 return res