python計算質(zhì)數(shù)的6種方法

更新時間：2023年05月30日 09:02:39 作者：ReisenSS

本文主要介紹了python計算質(zhì)數(shù)的6種方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

1.窮舉法

回想一下上課時學(xué)了變量、列表、循環(huán)語句之類的東西，sherry老師還親自演示了多重死循環(huán)是怎么搞出來的（老師是手滑了還是業(yè)務(wù)不熟練?。?，所以我們還是要仔細(xì)思考一下不要重蹈覆轍。

思路：首先要構(gòu)造一個循環(huán)，遍歷所有符合條件的自然數(shù)，然后一個一個驗(yàn)證是否為質(zhì)數(shù)，最后把符合條件的質(zhì)數(shù)列出來。

# 最開始編的窮舉法，簡單粗暴，就是性能拉跨。
# P=因數(shù)，N=自然數(shù)
import time
t0 = time.time()  # 開始時間
Min = 10  # 范圍最小值
Max = 30  # 范圍最大值
Result = []  # 結(jié)果
for N in range(Min, Max):  # 給自然數(shù)來個遍歷
    for P in range(2, N):
        if (N % P == 0):  # 判斷是否有因數(shù)
            break  # 有因數(shù)那就不是質(zhì)數(shù)，跳出循環(huán)
    else:
        Result.append(N)
print('計算', Min, '到', Max, '之間的質(zhì)數(shù)')
print(Min, '到', Max, '之間的質(zhì)數(shù)序列:', Result)
print(Min, '到', Max, '之間的質(zhì)數(shù)個數(shù):', len(Result))
print('計算耗時:', time.time() - t0, '秒')

執(zhí)行結(jié)果（計算耗時是最后加上去的）：

到這里作業(yè)就搞定了。然后把其他幾道題也做完了，發(fā)現(xiàn)很無聊，就又切回來想搞點(diǎn)事。這么點(diǎn)計算量，0秒真的有點(diǎn)少，不如趁這個機(jī)會烤一烤筆記本的性能，所以直接在Min和Max的值后面加幾個0。試試100000-200000。

很尷尬，直接卡住了，這代碼有點(diǎn)拉跨啊，完全不符合我的風(fēng)格。倒了杯咖啡，終于跑完了。

這個也太夸張，一定是哪里出了問題，很久以前用C寫的代碼我記得也沒那么慢啊。反正周末挺閑的，不如仔細(xì)研究一下。

2.函數(shù)（CV）大法

為了拓寬一下思路，我決定借鑒一下大佬的代碼。聽說函數(shù)是個好東西，所以就CV了兩個函數(shù)。

一個函數(shù)判斷質(zhì)數(shù)，另一個求范圍內(nèi)的所有質(zhì)數(shù)，把它們拼一起，是這個樣子：

# 網(wǎng)上學(xué)來的，自定義兩個函數(shù)，但是數(shù)值稍微大點(diǎn)就卡死了。
import time
t0 = time.time()
Min = 100000  # 范圍最小值
Max = 200000  # 范圍最大值
def is_prime(n): return 0 not in [n % i for i in range(2, n//2+1)]  # 判斷是否為質(zhì)數(shù)
def gen_prime(a, b): return [n for n in range(
    a, b+1) if 0 not in [n % i for i in range(2, n//2+1)]]  # 輸出范圍內(nèi)的質(zhì)數(shù)
print('計算', Min, '到', Max, '之間的質(zhì)數(shù)')
print(Min, '到', Max, '之間的質(zhì)數(shù)序列:', gen_prime(Min, Max))
print('計算耗時:', time.time() - t0, '秒')

稍微改動了一下，還是100000-200000，我們試試看。

嗯，一運(yùn)行風(fēng)扇就開始嘯叫，CPU都快烤炸了。看來CV大法也不行啊。經(jīng)過漫長的烤機(jī)，這次結(jié)果比上次還慘，300多秒，這兩個函數(shù)本質(zhì)上還是窮舉法，看來這條路也走不通。

3.窮舉法改

我們可以分析一下窮舉法的代碼，看看有沒有什么改進(jìn)的方法。首先，通過九年義務(wù)教育掌握的數(shù)學(xué)知識，我們知道，質(zhì)數(shù)中只有2是偶數(shù)，所以計算中可以把偶數(shù)忽略掉，只計算奇數(shù)，工作量立馬減半！其次，在用因數(shù)P判斷N是否為質(zhì)數(shù)時，如果P足夠大的話，比如說PxP>=N的時候，那么后面的循環(huán)其實(shí)是重復(fù)無意義的。因?yàn)榧僭O(shè)PxQ>=N，那么P和Q必然有一個小于sqrt(N)，只需要計算P<=sqrt(N)的情況就行了。

因?yàn)?作為唯一一個偶數(shù)，夾在循環(huán)里面處理起來很麻煩，所以放在開頭處理掉。最終的代碼如下：

# 優(yōu)化后的代碼，減少了一些無意義的循環(huán)，比以前快多了。
import time
t0 = time.time()
Min = 100000  # 范圍最小值
Max = 200000  # 范圍最大值
Prime = [2, 3]  # 質(zhì)數(shù)列表
Result = []  # 結(jié)果
Loop = 0  # 計算循環(huán)次數(shù)
if Min <= 2:
    Result.append(2)
if Min <= 3:
    Result.append(3)  # 先把2這個麻煩的偶數(shù)處理掉
for N in range(5, Max, 2):
    for P in range(3, int(N**0.5)+2, 2):  # 只計算到根號N
        Loop += 1
        if (N % P == 0):
            break
    else:
        Prime.append(N)
        if N > Min:
            Result.append(N)
print('計算', Min, '到', Max, '之間的質(zhì)數(shù)')
print(Min, '到', Max, '之間的質(zhì)數(shù)序列:', Result)
print(Min, '到', Max, '之間的質(zhì)數(shù)個數(shù):', len(Result))
print('循環(huán)次數(shù):', Loop)
print('計算耗時:', time.time() - t0, '秒')

代碼量雖然多了，但是效果還是很明顯，100000-200000才0.4秒，快了不知道多少，看來我們的思路是對的。我決定再加到1000000-5000000，看看能不能撐住。因?yàn)檩敵鎏嗔丝刂婆_會卡死，所以改一下，只輸出最后一個質(zhì)數(shù)。

總共花了64秒，看來還是有點(diǎn)費(fèi)勁。

4.窮舉法魔改

我們再來分析一下，如果我們用于判斷的因數(shù)，不是用奇數(shù)列表，而是用生成的Prime列表里面的質(zhì)數(shù)，因?yàn)橘|(zhì)數(shù)的個數(shù)遠(yuǎn)遠(yuǎn)少于奇數(shù)，所以第二個循環(huán)會少一些工作量呢？可以試試看。但是因?yàn)檫@個改動，需要加一些判斷語句進(jìn)去，所以節(jié)省的時間比較有限。

# 別看這個代碼比較長，但是跑到1000萬也不會卡死，而且還很快。
import time
t0 = time.time()
Min = 1000000  # 范圍最小值
Max = 5000000  # 范圍最大值
Prime = [2, 3]  # 質(zhì)數(shù)列表
Result = []  # 結(jié)果
Loop = 0  # 計算循環(huán)次數(shù)
if Min <= 2:
    Result.append(2)
if Min <= 3:
    Result.append(3)
for N in range(5, Max, 2):
    M = int(N**0.5)  # 上限為根號N
    for P in range(len(Prime)):  # 在質(zhì)數(shù)列表Prime中遍歷
        Loop += 1
        L = Prime[P+1]
        if (N % L == 0):
            break
        elif L >= M:  # 上限大于根號N，判斷為質(zhì)數(shù)并跳出循環(huán)
            Prime.append(N)
            if N > Min:
                Result.append(N)
            break
print('計算', Min, '到', Max, '之間的質(zhì)數(shù)')
print('最后一個質(zhì)數(shù):', Result[-1])
print(Min, '到', Max, '之間的質(zhì)數(shù)個數(shù):', len(Result))
print('循環(huán)次數(shù):', Loop)
print('計算耗時:', time.time() - t0, '秒')

還是1000000-5000000再試試看

這次耗時22秒，時間又縮短了一大半，但是好像已經(jīng)沒多少改進(jìn)的空間了，感覺窮舉法已經(jīng)到頭了，需要新的思路。

5.埃氏篩法

其實(shí)初中數(shù)學(xué)我們就學(xué)過埃氏篩法：如果P是質(zhì)數(shù)，那么大于P的N的倍數(shù)一定不是質(zhì)數(shù)。把所有的合數(shù)排除掉，那么剩下的就都是質(zhì)數(shù)了。我們可以生成一個列表用來儲存數(shù)字是否是質(zhì)數(shù)，初始階段都是質(zhì)數(shù)，每次得出一個質(zhì)數(shù)就將它的倍數(shù)全部標(biāo)記為合數(shù)。

# 速度已經(jīng)起飛了。
import time
t0 = time.time()
Min = 1000000  # 范圍最小值
Max = 2000000  # 范圍最大值
Loop = 0  # 計算循環(huán)次數(shù)
Result = []  # 結(jié)果
Natural = [True for P in range(Max)]  # 自然數(shù)列表標(biāo)記為True
for P in range(2, Max):
    if Natural[P]:  # 標(biāo)記如果為True，就是質(zhì)數(shù)
        if P >= Min:
            Result.append(P)  # 添加范圍之內(nèi)的質(zhì)數(shù)
        for N in range(P*2, Max, P):   # 將質(zhì)數(shù)的倍數(shù)的標(biāo)記改為False
            Loop += 1
            Natural[N] = False
print('計算', Min, '到', Max, '之間的質(zhì)數(shù)')
print('最后一個質(zhì)數(shù):', Result[-1])
print(Min, '到', Max, '之間的質(zhì)數(shù)個數(shù):', len(Result))
print('循環(huán)次數(shù):', Loop)
print('計算耗時:', time.time() - t0, '秒')

1.6秒，比最高級的窮舉法還要快上10多倍，這是數(shù)學(xué)的勝利。再試試1-50000000。

很不錯，只需要20秒。因?yàn)楹Y法的特性，忽略內(nèi)存的影響，數(shù)值越大，后面的速度反而越快了。

6.歐拉篩法

我們可以仔細(xì)分析一下，上面的埃氏篩法在最后標(biāo)記的時候，還是多算了一些東西，N會重復(fù)標(biāo)記False，比如77，既是7的倍數(shù)又是11的倍數(shù)，這樣會被標(biāo)記兩次，后面的大合數(shù)會重復(fù)標(biāo)記多次，浪費(fèi)了算力，所以標(biāo)記的時候要排除合數(shù)。另外就是P*N大于Max時，后面的計算已經(jīng)無意義了，也要跳出來。把這些重復(fù)的動作排除掉，就是歐拉篩法，也叫線性篩。

# 最終版，優(yōu)化了很多細(xì)節(jié)。
import time
t0 = time.time()
Min = 1  # 范圍最小值
Max = 50000000  # 范圍最大值
Loop = 0  # 計算循環(huán)次數(shù)
Prime = [2]
Result = []  # 結(jié)果
if Min <= 2:
    Result.append(2)
Limit = int(Max/3)+1
Natural = [True for P in range(Max+1)]  # 自然數(shù)列表標(biāo)記為True
for P in range(3, Max+1, 2):
    if Natural[P]:  # 標(biāo)記如果為True，就是質(zhì)數(shù)
        Prime.append(P)
        if P >= Min:
            Result.append(P)
    if P > Limit:  # 超過Limit不需要再篩了，直接continue
        continue
    for N in Prime:   # 將質(zhì)數(shù)的倍數(shù)的標(biāo)記改為False
        Loop += 1
        if P*N > Max:  # 超過Max就無意義了，直接break
            break
        Natural[P * N] = False
        if P % N == 0:  # 判斷是否為合數(shù)
            break
print('計算', Min, '到', Max, '之間的質(zhì)數(shù)')
print('最后一個質(zhì)數(shù):', Result[-1])
print(Min, '到', Max, '之間的質(zhì)數(shù)個數(shù):', len(Result))
print('循環(huán)次數(shù):', Loop)
print('計算耗時:', time.time() - t0, '秒')

（因?yàn)橹暗陌姹究s進(jìn)錯了，所以更新了這段代碼）