python求質(zhì)數(shù)的3種方法

更新時(shí)間：2018年09月28日 09:42:31 作者：z大醬

這篇文章主要為大家詳細(xì)介紹了python求質(zhì)數(shù)的多種方法，多種方法求質(zhì)數(shù)的實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文為大家分享了多種方法求質(zhì)數(shù)python實(shí)現(xiàn)代碼，供大家參考，具體內(nèi)容如下

題目要求是求所有小于n的質(zhì)數(shù)的個(gè)數(shù)。

求質(zhì)數(shù)方法1：

窮舉法：
根據(jù)定義循環(huán)判斷該數(shù)除以比他小的每個(gè)自然數(shù)（大于1），如果有能被他整除的就不是質(zhì)數(shù)：

def countPrimes1(self, n):
  """
  :type n: int
  :rtype: int
  """
  if n<=2:
   return 0
  else:
   res=[]
  for i in range(2,n):
   flag=0 # 質(zhì)數(shù)標(biāo)志，=0表示質(zhì)數(shù)
   for j in range(2,i):
    if i%j ==0:
     flag=1
   if flag==0:
    res.append(i)
  return len(res)

求質(zhì)數(shù)方法2：

利用定理：如果一個(gè)數(shù)是合數(shù)，那么它的最小質(zhì)因數(shù)肯定小于等于它的平方根。所以判斷一個(gè)數(shù)是否是質(zhì)數(shù)，只需判斷它是否能被小于它開(kāi)根后的所有數(shù)整除。這樣做的運(yùn)算會(huì)少很多。

 def countPrimes2(self, n):
  if n<=2:
   return 0
  else:
   res=[]
  for i in range(2, n):
   flag=0
   for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
     flag = 1
   if flag == 0:
    res.append(i)
  return len(res)

求質(zhì)數(shù)方法3：

利用定理：如果一個(gè)數(shù)是合數(shù)，那么它的最小質(zhì)因數(shù)肯定小于等于它的平方根。我們可以發(fā)現(xiàn)只要嘗試小于等于平方根的所有數(shù)即可。列舉從 3 到根號(hào)x的所有數(shù)，還是有些浪費(fèi)。比如要判斷101是否質(zhì)數(shù)，101的根號(hào)取整后是10，需要嘗試的數(shù)是1到10。但是可以發(fā)現(xiàn)，對(duì)9的嘗試是多余的。不能被3整除，必然不能被9整除……順著這個(gè)思路走下去，其實(shí)，只要嘗試小于根號(hào)x的質(zhì)數(shù)即可。而這些質(zhì)數(shù)，恰好前面已經(jīng)算出來(lái)了，已經(jīng)存在res中了。

 def countPrimes3(self, n):
  if n <= 2:
   return 0
  else:
   res = []
  for i in range(2, n):
   flag = 0
   for j in res:
    if i % j == 0:
     flag = 1
   if flag == 0:
    res.append(i)
  return len(res)

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

Python條件分支?if?語(yǔ)句全講解(一文掌握)
在Python編程中,布爾運(yùn)算符有明確的優(yōu)先級(jí)順序,影響代碼邏輯判斷,從高到低依次是:括號(hào)()、not、and、or,括號(hào)用于明確運(yùn)算順序,not具有次高優(yōu)先級(jí),影響單個(gè)布爾值,and和or則根據(jù)優(yōu)先級(jí)順序結(jié)合布爾值,正確理解和應(yīng)用這些優(yōu)先級(jí)對(duì)于編寫(xiě)有效和準(zhǔn)確的條件語(yǔ)句至關(guān)重要
2024-10-10
python破解zip加密文件的方法
這篇文章主要介紹了python破解zip加密文件的方法,本文圖文并茂給大家介紹的非常詳細(xì)，需要的朋友可以參考下
2018-05-05
python實(shí)現(xiàn)21點(diǎn)小游戲
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)21點(diǎn)小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-04-04
Python從ZabbixAPI獲取信息及實(shí)現(xiàn)Zabbix-API 監(jiān)控的方法
這篇文章主要介紹了Python從ZabbixAPI獲取信息及實(shí)現(xiàn)Zabbix-API 監(jiān)控的方法,需要的朋友可以參考下
2018-09-09
python爬取抖音視頻的實(shí)例分析
在本篇內(nèi)容里小編給大家整理一篇關(guān)于python爬取抖音視頻的實(shí)例分析的相關(guān)內(nèi)容，有興趣的朋友可以測(cè)試下實(shí)例內(nèi)容。
2021-01-01
Django自定義權(quán)限及用戶分組
這篇文章主要為大家介紹了Django登錄權(quán)限及分組模板使用權(quán)限，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
2022-06-06
基于Python繪制三種不同的中國(guó)結(jié)
馬上就要迎來(lái)新年了，就繪制了幾個(gè)中國(guó)結(jié)，嘿嘿！本文為大家整理了三個(gè)繪制中國(guó)結(jié)的方法，文中的示例代碼講解詳細(xì)，快跟隨小編一起動(dòng)手嘗試一下吧
2023-01-01
scrapy-redis分布式爬蟲(chóng)的搭建過(guò)程(理論篇)
這篇文章主要介紹了scrapy-redis分布式爬蟲(chóng)的搭建過(guò)程(理論篇)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2020-09-09
Python3如何日志同時(shí)輸出到控制臺(tái)和文件
這篇文章主要介紹了Python3如何日志同時(shí)輸出到控制臺(tái)和文件問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2023-11-11
利用python繪制二三維曲面和矢量流線圖的代碼示例
這篇文章主要給大家詳細(xì)介紹了如何利用python繪制二三維曲面和矢量流線圖，文中通過(guò)代碼示例介紹的非常詳細(xì)，對(duì)我們學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下
2023-07-07