（leetcode204）计数质数（暴力法及其优化，厄拉多塞筛法）

暴力法及其优化是笔者的思路和代码，厄拉多塞筛法是学习这篇题解后手写的，（据说还有更快的算法线性筛之类的，，这数学也太顶了）
原题如下：

1、暴力法及其优化

1、对每个小于n的数x都遍历一遍。
2、判断x是否为素数，看是否能被小于x的数整除。
复杂度为O（n2）。
在第二步中，可以不必判断小于x的所有数字，只需要判断[2,√n]之间的数字，例如26，只需判断[2,5]之间的数字即可，因为对后面可能出现的因子，他所对应的因子都会在√n之前出现，比如13，因为已经在2的时候判断过了，就不必再次判断。
代码如下：

import math
class Solution:
    def countPrimes(self, n: int) -> int:
    	#这里是针对本题，小于3的数字，没有更小的素数
    	#对于大于等于3的数字，默认有个2，所以ret初始值为1
    	#之所以把2拿出来是为了后续判断素数的时候，直接去除偶数
        if n<3:
            return 0
        ret=1
        for item in range(3,n):
            if item&1:
                flag=1
                t=int(math.sqrt(item))
                for i in range(2,t+1):
                    x=item//i
                    if x*i==item:
                        flag=0
                        break
                if flag:
                    #print(item)
                    ret+=1
        return ret

        

2、厄拉多塞筛法

原题解链接在文章开始处，此处为笔者理解。
是一种以空间换时间的思路，需要一个长为n的辅助数组lst。
lst初始值全为1，1表示是质数。
从2到n-1的每个数字t，

（1）如果当前位置lst[t]是1，则为质数，对于从t*2,t*3,...
直到n-1之前的每个位置均记为0，表示是由当前质数所构成的合数。
（2）如果当前位置为0，表示在之前某次判断中已经判定这个数字是合数，
continue即可。

如何理解呢？
如果我们判断到这个数t的时候lst[t]依然是1，说明之前所有的循环都没有改变这个位置，即比t小的所有质数都不能组成他，也就是i是质数。

这里存在一个优化，在（1）中，我们不必从i2开始，而可以直接从ii开始，因为i2，i3…这些已经在2、3…的判断中判定过了，不必重复置位。

import math
class Solution:
    def countPrimes(self, n: int) -> int:
        if n<3:
            return 0
        lst=[1]*n
        #√n之后的所有合数都至少有1个因子在√n之前，
        #因为如果都在后面的话乘积一定大于n，
        #这样我们就不用判断√n之后的数字了
        for index in range(2,int(math.sqrt(n)+1)):
            if lst[index]:
                j=index*index
                while j<n:
                    lst[j]=0
                    j+=index
        #减2是为了去掉lst[0],lst[1]中的数字1
        return sum(lst)-2