快捷導(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ì)，對大家的學(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)簡稱埃氏篩法，是古希臘數(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

conda虛擬環(huán)境中查看包的位置的四種方法
本文主要介紹了conda虛擬環(huán)境中查看包的位置的四種方法,包括使用Conda命令、在Python中查看、使用pip命令以及檢查環(huán)境目錄結(jié)構(gòu),具有一定的參考價(jià)值,感興趣的可以了解一下
2025-03-03
Pandas DataFrame數(shù)據(jù)的更改、插入新增的列和行的方法
這篇文章主要介紹了Pandas DataFrame數(shù)據(jù)的更改、插入新增的列和行的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2019-06-06
Python使用fliecmp實(shí)現(xiàn)比較文件的操作
對于文件的比較一般有幾種，比如比較文件的內(nèi)容，比較文件的大小，或者直接對比整個(gè)項(xiàng)目文件，本文就詳細(xì)的介紹這些方法的實(shí)現(xiàn)，感興趣的可以了解一下
2021-06-06
Python中的單下劃線和雙下劃線使用場景詳解
這篇文章主要介紹了Python中的單下劃線和雙下劃線使用場景詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2019-09-09
Python包管理利器之pip命令的安裝與使用入門指南
pip是Python的包管理工具,全稱為"Pip?Installs?Packages",是Python生態(tài)系統(tǒng)中最重要的工具之一,下面就跟隨小編一起深入了解下pip命令的安裝與使用吧
2025-04-04
Python使用單例模式創(chuàng)建類的實(shí)現(xiàn)示例
本文詳細(xì)介紹了Python中實(shí)現(xiàn)單例模式的多種方式,包括元類、threading.Lock、模塊、importlib、__new__方法和裝飾器等,感興趣的可以了解一下
2024-12-12
快速了解Python相對導(dǎo)入
這篇文章主要介紹了快速了解Python相對導(dǎo)入，具有一定借鑒價(jià)值,需要的朋友可以參考下
2018-01-01
利用Python和C++實(shí)現(xiàn)解析gltf文件
gltf是類似于stl、obj、ply等常見的3D對象存儲格式,它被設(shè)計(jì)出來是為了便于渲染的數(shù)據(jù)轉(zhuǎn)換和傳輸,本文為大家介紹了使用Python和C++解析gltf文件的方法,感興趣的可以了解下
2023-09-09
Python中處理表格數(shù)據(jù)的Tablib庫詳解
這篇文章主要介紹了Python中處理表格數(shù)據(jù)的Tablib庫詳解,Tablib 是一個(gè) MIT 許可的格式不可知的表格數(shù)據(jù)集庫，用 Python 編寫,它允許您導(dǎo)入、導(dǎo)出和操作表格數(shù)據(jù)集,需要的朋友可以參考下
2023-08-08
對pycharm代碼整體左移和右移縮進(jìn)快捷鍵的介紹
今天小編就為大家分享一篇對pycharm代碼整體左移和右移縮進(jìn)快捷鍵的介紹，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧
2018-07-07