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

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

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

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

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

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

窮舉法：
根據(jù)定義循環(huán)判斷該數(shù)除以比他小的每個自然數(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ù)標志，=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：

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

 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：

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

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

python項目下生成requirements.txt方法
這篇文章主要介紹了python項目下生成requirements.txt的方法，很多小伙伴不知道如何生成requirements.txt，本文就通過代碼示例給大家詳細介紹如何生成，,需要的朋友可以參考下
2023-06-06
Python功能點實現(xiàn):函數(shù)級/代碼塊級計時器
今天小編就為大家分享一篇關于Python功能點實現(xiàn):函數(shù)級/代碼塊級計時器，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
2019-01-01
Python循環(huán)控制詳解
本文介紹了Python編程語言中關于for循環(huán)和if條件控制的一些基本使用,包含了單層循環(huán)的退出機制和多層循環(huán)的退出機制,使得我們在滿足特定條件時,可以直接結(jié)束多層循環(huán),需要的朋友可以參考下
2024-07-07
深度解析Python線程和進程
這篇文章主要介紹了Python線程和進程的相關知識,包括線程與進程的區(qū)別，通過示例代碼介紹了進程與線程的操作方法，需要的朋友可以參考下
2022-04-04
如何通過Python實現(xiàn)標簽云算法
這篇文章主要介紹了如何通過Python實現(xiàn)標簽云算法,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2019-07-07
基于Python2、Python3中reload()的不同用法介紹
今天小編就為大家分享一篇基于Python2、Python3中reload()的不同用法介紹，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-08-08
安裝PyTorch的詳細過程記錄
PyTorch是一個基于Python的科學計算框架,用于進行深度學習相關研究,下面這篇文章主要給大家介紹了關于安裝PyTorch的詳細過程,文中通過圖文介紹的非常詳細,需要的朋友可以參考下
2022-03-03
python通過socket搭建極簡web服務器的實現(xiàn)代碼
python的web框架眾多,常見的如django、flask、tornado等,其底層是什么還是有些許的疑問,所以查找相關資料,實現(xiàn)瀏覽器訪問,并返回相關信息,本文將給大家介紹python通過socket搭建極簡web服務器,需要的朋友可以參考下
2023-10-10
解讀sqlalchemy的常用數(shù)據(jù)類型有哪些
這篇文章主要介紹了解讀sqlalchemy的常用數(shù)據(jù)類型有哪些，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-03-03
python實現(xiàn)mask矩陣示例(根據(jù)列表所給元素)
這篇文章主要介紹了python實現(xiàn)mask矩陣示例(根據(jù)列表所給元素),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2020-07-07