天天看點

(leetcode204)計數質數(暴力法及其優化,厄拉多塞篩法)1、暴力法及其優化2、厄拉多塞篩法

暴力法及其優化是筆者的思路和代碼,厄拉多塞篩法是學習這篇題解後手寫的,(據說還有更快的算法線性篩之類的,,這數學也太頂了)

原題如下:

(leetcode204)計數質數(暴力法及其優化,厄拉多塞篩法)1、暴力法及其優化2、厄拉多塞篩法

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