快捷導(dǎo)航

Python計算素數(shù)個數(shù)的兩種方法

更新時間：2023年05月19日 09:10:19 作者：機器學(xué)習(xí)Zero

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

方法一：直接判斷

from math import sqrt
def isPrime(n):
? ? for i in range(2,int(sqrt(n))+1):
? ? ? ? if n%i==0:
? ? ? ? ? ? return False
? ? return True
def countPrime(N):
? ? if N<3:
? ? ? ? return 0
? ? else:
? ? ? ? cou = 1
? ? ? ? for i in range(3,N,2):
? ? ? ? ? ? if isPrime(i):
? ? ? ? ? ? ? ? cou += 1
? ? return cou
print(countPrime(2))
print(countPrime(5))
print(countPrime(100))
print(countPrime(100000)) ?
print(countPrime(10000000))#在n>100000000時達到計算瓶頸

輸出：

0
2
25
9592
664579

方法二：埃氏篩法

埃拉托色尼篩選法(the Sieve of Eratosthenes)簡稱埃氏篩法，是古希臘數(shù)學(xué)家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一種篩選法。

要得到自然數(shù)n以內(nèi)的全部素數(shù)，必須把不大于n的所有素數(shù)的倍數(shù)剔除，剩下的就是素數(shù)，具體步驟如下：先用2去篩，即把2留下，把2的倍數(shù)剔除掉；再用下一個質(zhì)數(shù)，也就是3篩，把3留下，把3的倍數(shù)剔除掉；接下去用下一個質(zhì)數(shù)5篩，把5留下，把5的倍數(shù)剔除掉；不斷重復(fù)下去。

def couPrime(N):
    primeList = [True]*N
    for i in range(2,N):
        if(primeList[i]):
            for j in range(2*i,N,i):
                primeList[j]=False
    cou = primeList.count(True)-2
    return cou
print(couPrime(100000000)) #在n>1000000000達到計算瓶頸

輸出：