快捷導(dǎo)航

Python計(jì)算素?cái)?shù)個(gè)數(shù)的兩種方法

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

本文主要介紹了Python計(jì)算素?cái)?shù)個(gè)數(shù)的兩種方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(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時(shí)達(dá)到計(jì)算瓶頸

輸出：

0
2
25
9592
664579

方法二：埃氏篩法

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

要得到自然數(shù)n以內(nèi)的全部素?cái)?shù)，必須把不大于n的所有素?cái)?shù)的倍數(shù)剔除，剩下的就是素?cái)?shù)，具體步驟如下：先用2去篩，即把2留下，把2的倍數(shù)剔除掉；再用下一個(gè)質(zhì)數(shù)，也就是3篩，把3留下，把3的倍數(shù)剔除掉；接下去用下一個(gè)質(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達(dá)到計(jì)算瓶頸

輸出：

5761455

到此這篇關(guān)于Python計(jì)算素?cái)?shù)個(gè)數(shù)的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Python計(jì)算素?cái)?shù)個(gè)數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: