（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