java循环1000000000_求十亿内所有质数的和，怎么做最快?
注：對(duì)知乎的公式編輯功能實(shí)在無(wú)力吐槽，用typora寫的文章直接粘過(guò)來(lái)公式無(wú)法顯示，只好又手工加上了全部公式，不過(guò)可能還是會(huì)有遺漏。大家可以點(diǎn)擊這個(gè)鏈接 查看我的博客原文。以下是正文：
第一次關(guān)注到這個(gè)問(wèn)題是在做project euler第10題的時(shí)候，原題目是要求兩百萬(wàn)以內(nèi)質(zhì)數(shù)的和，知乎的題目把這個(gè)數(shù)字調(diào)到了10億，事實(shí)證明這個(gè)規(guī)模調(diào)整是決定性的，很多在小規(guī)模可用的算法在10億這個(gè)規(guī)模都不可用了。和其它歐拉工程的題目類似，這個(gè)題目存在一個(gè)很明顯的暴力解法，但也存在一些效率更高的算法。暴力解法要不是通過(guò)對(duì)N以下的每個(gè)奇數(shù)做素性測(cè)試，要不是通過(guò)埃拉托斯特尼篩或者其它線性與亞線性篩得到N以下的所有質(zhì)數(shù)然后相加，如菜魚ftfish所言，這種暴力算法存在素?cái)?shù)個(gè)數(shù)決定的時(shí)間復(fù)雜度下限，所以肯定還存在更優(yōu)的算法?？梢詢?yōu)化的根本原因在于，要計(jì)算N以下所有質(zhì)數(shù)的和并不需要知道N以下的所有質(zhì)數(shù)。在此基礎(chǔ)上，我們可以使用各種技巧來(lái)提升算法的表現(xiàn)。
這個(gè)答案下目前最快的算法應(yīng)該就是菜魚ftfish所列的Lucy Hedgehog給出的算法，這個(gè)算法d在兩個(gè)方面讓人好奇，第一是效率極高，在時(shí)間和空間復(fù)雜度上的表現(xiàn)都極為優(yōu)異，甚至對(duì)于python這種較慢的腳本語(yǔ)言計(jì)算十億內(nèi)的質(zhì)數(shù)和都可以在一秒內(nèi)出結(jié)果，而我自己用python寫的的暴力算法甚至完全無(wú)法處理這個(gè)數(shù)據(jù)規(guī)模。第二是算法中采用了動(dòng)態(tài)規(guī)劃的思路，給出了一個(gè)求解質(zhì)數(shù)和的遞推式，讓人非常好奇作者是怎么想到的，以及這個(gè)遞推式背后有沒(méi)有更為一般和深刻的原理。可惜的是這個(gè)代碼可能由于過(guò)度優(yōu)化導(dǎo)致可讀性變得很差，原作者在論壇里也沒(méi)有做詳細(xì)的解釋，因此在好奇心驅(qū)使下，我仔細(xì)做了一點(diǎn)研究，讀了一些相關(guān)文獻(xiàn)，對(duì)不同的算法做了嘗試，最終實(shí)現(xiàn)了四個(gè)不同的算法版本。我想知道自己能不能寫出一個(gè)更快的算法，因?yàn)槲易约旱闹髁φZ(yǔ)言也是python，和Hedgehog使用的語(yǔ)言相同，在同種語(yǔ)言下的比較應(yīng)該是相對(duì)公平的。事實(shí)表明僅有一個(gè)算法在小規(guī)模上數(shù)據(jù)上的表現(xiàn)比Hedgehog的算法要更好，但在大規(guī)模數(shù)據(jù)上，Hedgehog的算法仍然是最穩(wěn)健的。下面列的是我的四個(gè)算法和Hedgehog算法的對(duì)比：
圖中橫軸表示數(shù)據(jù)規(guī)模的對(duì)數(shù)，縱軸表示運(yùn)行時(shí)間的對(duì)數(shù)。在我寫的這四個(gè)算法中，表現(xiàn)最好的是hedgehog_recursive這個(gè)算法，使用帶備忘錄的自上而下動(dòng)態(tài)規(guī)劃方法實(shí)現(xiàn)了Hedgehog算法中的原理，奇怪的是這個(gè)算法雖然只是直接翻譯了菜魚ftfish的數(shù)學(xué)推導(dǎo)，卻在小數(shù)據(jù)規(guī)模上表現(xiàn)到如此之好，基本上耗時(shí)都在Hedgehog算法的3%以內(nèi)，這不點(diǎn)我也不是很理解。其次表現(xiàn)類似的是sum_primes_sieve和legendre這兩個(gè)算法，前面這個(gè)算法使用了一個(gè)改進(jìn)的埃拉托斯特尼篩，而后者則是對(duì)法國(guó)數(shù)學(xué)家勒讓德提出的一個(gè)計(jì)算N以下素?cái)?shù)個(gè)數(shù)的遞推式的推廣，使其可以計(jì)算N以下素?cái)?shù)的和，我猜測(cè)這也是Hedgehog使用的遞推式的靈感來(lái)源。表現(xiàn)再次的是meissel這個(gè)算法，它依據(jù)的是德國(guó)天文學(xué)家對(duì)勒讓德計(jì)算N以下素?cái)?shù)個(gè)數(shù)算法的改進(jìn)，并將其推廣到可以計(jì)算素?cái)?shù)的和，理論上這個(gè)算法應(yīng)比勒讓德的算法更優(yōu)，但實(shí)際算法表現(xiàn)并沒(méi)有更好，可能是我的算法實(shí)現(xiàn)的原因。
下面我具體介紹一下以上四種算法的基本原理和代碼實(shí)現(xiàn)，我相信在代碼上還有很多優(yōu)化的空間，大家如果有什么改進(jìn)意見(jiàn)敬請(qǐng)?zhí)岢鰜?lái)。
一、改進(jìn)的埃拉托斯特尼篩
要求N以下的所有質(zhì)數(shù)的和，一個(gè)顯而易見(jiàn)的原理是用N以下所有自然數(shù)的和減去所有合數(shù)的和，自然數(shù)的和可以直接用求和公式計(jì)算，問(wèn)題在于篩選出所有合數(shù)并求和，顯然這里可以先用埃拉托斯特尼篩篩選出?以內(nèi)的所有質(zhì)數(shù)，才依次篩選出這些質(zhì)數(shù)在N以下的倍數(shù)并求和，這里的問(wèn)題是有些倍數(shù)被重復(fù)計(jì)算了，可以用某些歐拉篩來(lái)避免重復(fù)篩選，或者也可以用python的集合來(lái)去重，我這里使用的是后者，因?yàn)榻?jīng)過(guò)嘗試我發(fā)現(xiàn)用集合去重比用算法來(lái)避免重復(fù)篩選效率更高。
以上的算法明顯還可以繼續(xù)改進(jìn)，首先想到所有除二以外的質(zhì)數(shù)都為奇數(shù)，所以只需在奇數(shù)中篩選即可，再用所有奇數(shù)的和減去奇合數(shù)的和即可。進(jìn)一步的，我們知道所有大于三的素?cái)?shù)都可以表示成為?
的形式，因此我們只需要列出所有
?形式的數(shù)，用求和公式計(jì)算其總和，再篩選其中的合數(shù)并求和(同樣用集合來(lái)去重)，兩者相減即為N 以下所有質(zhì)數(shù)的和。算法的代碼實(shí)現(xiàn)比較簡(jiǎn)單，我這里就不多做解釋了。
from sympy import primerange
from math import floor
?
def sum_primes_sieve(n=2e6):
primes = list(primerange(2,n**0.5+1))
j = floor(n/6)
total_sum = 6*j*(j+1)
res_set = set()
for p in primes[2:]:
k = p
while p*k < n:
res_set.add(p*k)
k += 4 if k%6==1 else 2
ans = total_sum - sum(res_set)
return ans+5
二、Hedgehog算法的遞歸版本
菜魚ftfish解釋了Hedgehog算法的基本原理，其核心是答案中所列的遞推式，使得我們可以用動(dòng)態(tài)規(guī)劃來(lái)解決質(zhì)數(shù)和的問(wèn)題。Hedgehog算法中顯然使用的是自下而上的動(dòng)態(tài)規(guī)劃，我好奇用自上而下的動(dòng)態(tài)規(guī)劃會(huì)如何表現(xiàn)。因此，我使用遞歸函數(shù)直接翻譯了菜魚ftfish對(duì)這個(gè)算法的解釋，并使用python中functools模塊中的lru_cache裝飾器，實(shí)現(xiàn)算法的記憶化，這里免去自己寫備忘錄代碼的麻煩。這個(gè)算法是我所花時(shí)間最短，但卻是表現(xiàn)最好的算法，甚至在小規(guī)模數(shù)據(jù)上要好于Hedgehog的原始算法，這也是我感覺(jué)奇怪的地方。我猜測(cè)原因可能是在這里的動(dòng)態(tài)規(guī)劃中，有很多中間數(shù)據(jù)無(wú)需計(jì)算，自上而下的動(dòng)態(tài)規(guī)劃可以直接跳過(guò)這些數(shù)據(jù)，回到初始的邊界條件，而自下而上的動(dòng)態(tài)規(guī)劃則必需一步步的計(jì)算，才能得到最終的計(jì)算結(jié)果。這個(gè)算法的最大問(wèn)題在于處理大規(guī)模數(shù)據(jù)時(shí)遞歸深度過(guò)深的問(wèn)題，根據(jù)這個(gè)算法，其遞歸樹的深度約為
?，如果要計(jì)算十億內(nèi)質(zhì)數(shù)的和，則遞歸深度要達(dá)到31622層，而在我的python版本允許的最大遞歸深度僅為3000層，雖然可以自己修改python允許的最大遞歸深度，但python仍然會(huì)報(bào)“超過(guò)最大遞歸深度”的錯(cuò)誤，所以這個(gè)算法能夠處理的最大問(wèn)題規(guī)模大約就在兩百萬(wàn)左右，再大就無(wú)法保證正確執(zhí)行了?？赡芸梢允褂梦策f歸的方法來(lái)解決這個(gè)問(wèn)題，但python對(duì)尾遞歸優(yōu)化的支持并不好，我并沒(méi)有嘗試，如果有人嘗試成功了，可以分享一下經(jīng)驗(yàn)。
from functools import lru_cache
from sympy import isprime
from math import floor
?
@lru_cache(maxsize=32)
def s(v,p):
if v == 1:
return 0
if v == 2:
return 2
if p == 1:
return (2+v)*(v-1)/2
if p**2<=v and isprime(p):
return s(v,p-1)-p*(s(floor(v/p),p-1)-s(p-1,p-1))
else:
return s(v,p-1)
?
def hedgehog_recursive(n=2e6):
p = int(n**0.5) + 1
return s(n,p)
三、勒讓德算法
計(jì)算N以下所有素?cái)?shù)的和似乎在數(shù)論領(lǐng)域并不是一個(gè)重要的問(wèn)題，我看了一些文獻(xiàn)，只在部分文獻(xiàn)里看過(guò)對(duì)這個(gè)質(zhì)數(shù)和的漸進(jìn)估計(jì)，但并沒(méi)有看到給出確切的質(zhì)數(shù)和的值的算法分析。但是計(jì)算N以下的所有素?cái)?shù)的個(gè)數(shù)的問(wèn)題則是數(shù)論中的熱門話題了，相關(guān)文獻(xiàn)連篇累牘，因?yàn)檫@個(gè)問(wèn)題在數(shù)論領(lǐng)域有相當(dāng)?shù)闹匾?#xff0c;甚至還有一個(gè)專門的函數(shù)
?表示小于等于
?的所有素?cái)?shù)的個(gè)數(shù)。高斯和勒讓德通過(guò)經(jīng)驗(yàn)統(tǒng)計(jì)的方式猜測(cè)
?，這個(gè)猜想在1896年得到證明成為素?cái)?shù)定理，這是解析數(shù)論領(lǐng)域的最重要的成就之一。黎曼猜想也是在改進(jìn)對(duì)
?的估計(jì)中被提出來(lái)的，現(xiàn)在應(yīng)該是數(shù)論領(lǐng)域最重要的未被證明的猜想。除開解析數(shù)論的進(jìn)路以外，很多數(shù)學(xué)家也在不斷改進(jìn)計(jì)算?
的確切值的算法，相關(guān)的研究進(jìn)展大家可以參見(jiàn)這個(gè)維基頁(yè)面，更深入的研究可以參見(jiàn)我在文末列出的參考文獻(xiàn)。
我們對(duì)計(jì)算N以下素?cái)?shù)和算法來(lái)源于對(duì)勒讓德對(duì)計(jì)算N以下素?cái)?shù)個(gè)數(shù)的算法的推廣。在勒讓德以前，數(shù)學(xué)家們計(jì)算?
的方法就是篩選出
?以下的所有素?cái)?shù)然后數(shù)個(gè)數(shù)，勒讓德首次指出，為了計(jì)算?
，我們并不需要知道
?以下的所有素?cái)?shù)，只需要知道?
就可以了。他給出的算法基于容斥原理。我們?cè)O(shè)
?表示小于等于?
的數(shù)中不能被?
整除的數(shù)的個(gè)數(shù)，其中
?表示前?
個(gè)質(zhì)數(shù)，如
?等等。則有：
其中
?表示下取整。這個(gè)公式的意思是為了計(jì)算小于等于
?不能被?
整除的數(shù)的個(gè)數(shù)，我們從
?中減去可以
被?整除的數(shù)的個(gè)數(shù)，但是這樣同時(shí)被兩個(gè)質(zhì)數(shù)整除的數(shù)就重復(fù)減去了，所以我們需要把它們的個(gè)數(shù)加回來(lái)，但是這樣又會(huì)導(dǎo)致對(duì)可以同時(shí)被三個(gè)質(zhì)數(shù)整除重復(fù)加入了，所以我們需要減去這樣的數(shù)的個(gè)數(shù)，之后依次類推，顯然這只是容斥原理的一個(gè)簡(jiǎn)單應(yīng)用。如果真的要用這個(gè)公式來(lái)計(jì)算
?仍然顯得比較復(fù)雜，通過(guò)仔細(xì)分析
?的算法，我們可以發(fā)現(xiàn)一個(gè)遞推式。我們定義
?，而?
顯然表示小于等于?
的數(shù)中所有奇數(shù)的個(gè)數(shù)，則有：
這個(gè)公式同樣可以使用證明容斥原理時(shí)使用的數(shù)學(xué)歸納法加以證明，詳細(xì)的證明我就不寫了，只說(shuō)明一下
?的簡(jiǎn)單情況：
有了這個(gè)遞推式和上面給出的邊界條件，我們就可以計(jì)算出
?。如果我們?cè)O(shè)
?，則
?實(shí)際上表示是
?到?
之間素?cái)?shù)的個(gè)數(shù)，則可以得到：
因而我們可據(jù)此算出
?以下的素?cái)?shù)個(gè)數(shù)。可以看出，勒讓德的算法將?
以下所有質(zhì)數(shù)分成了兩部分，然后分別計(jì)算它們的個(gè)數(shù)，加起來(lái)即為
?以下所有質(zhì)數(shù)的個(gè)數(shù)。我們計(jì)算N以下質(zhì)數(shù)和的算法也是基于同樣的原理，我們?cè)O(shè)?
表示小于等于
?的數(shù)中不能被
?整除的數(shù)的和，其中
?表示前
?個(gè)質(zhì)數(shù)，則?
顯然表示小于等于?的數(shù)中所有奇數(shù)的和，則我們可以得到以下遞推式：
和上面類似，我們只說(shuō)明一下
?的簡(jiǎn)單情況，定義
?表示?
的自然數(shù)之和，如我們有
?，則有：
如我們?cè)O(shè)
?表示小于等于
?的所有素?cái)?shù)的和，并設(shè)
?則根據(jù)和上面類似的原理，我們有：
據(jù)此我們可以求出小于等于
?的所有質(zhì)數(shù)的和?？梢钥吹竭@里的遞推式和Hedgehog算法的遞推式非常相似，區(qū)別在于這里的遞推式中
?表示素?cái)?shù)，則不需要像Hedgehog算法那樣需要判斷是否為素?cái)?shù)。更重要的區(qū)別在于如果使用遞歸實(shí)現(xiàn)Hedgehog算法，則其遞歸深度為?
，而在這里的算法中，遞歸深度為
?，前者明顯大于后者，因而這里的算法可以更快的達(dá)到邊界條件，并且因?yàn)樗財(cái)?shù)越大則分布密度越低，則兩者在大規(guī)模數(shù)據(jù)中差距會(huì)更加明顯。如當(dāng)
?時(shí)，
?，而
?，前者的遞歸深度是后者的四倍。
勒讓德算法的缺陷和第二個(gè)算法類似，都會(huì)在大規(guī)模數(shù)據(jù)上因?yàn)榈疃鹊膯?wèn)題而無(wú)法計(jì)算，雖然勒讓德算法已經(jīng)大大減少了遞歸函數(shù)的遞歸深度，但減少的仍然不夠。如要計(jì)算十億以內(nèi)的素?cái)?shù)和，則勒讓德算法的遞歸深度為
?，仍然超過(guò)python允許的最大遞歸深度。因此我們需要進(jìn)一步縮減遞歸深度，meissel算法就是一個(gè)有趣的深度。
勒讓德算法的代碼實(shí)現(xiàn)如下：
from sympy import primerange,isprime
from functools import lru_cache
?
def legendre(n=2e6):
primes = list(primerange(1,int(n**0.5)+1))
@lru_cache(maxsize=8192)
def sigma(x,a):
if a == 1:
return (x//2)**2 if x%2==0 else (x//2+1)**2
elif x <= primes[a-1]:
return 1
else:
return sigma(x,a-1) - primes[a-1]*sigma(x//primes[a-1],a-1)
a = len(primes)
res = sigma(n,a) + sum(primes) - 1
return res
四、meissel算法
19世紀(jì)晚期，德國(guó)天文學(xué)家E. Meissel以上提到的勒讓德算法進(jìn)行了改進(jìn)，進(jìn)一步提升了計(jì)算
?的效率，他使用自己改進(jìn)的算法計(jì)算了
?，雖然比正確值小了56，不過(guò)考慮到他完全依靠手工計(jì)算，這個(gè)準(zhǔn)確度已經(jīng)非常驚人了。Meissel對(duì)勒讓德算法的主要改進(jìn)是加入了一個(gè)新項(xiàng)
?，從而使得算法的時(shí)間復(fù)雜度從勒讓德算法的
?改進(jìn)到
?，空間復(fù)雜度從
?改進(jìn)至
?。這里我們對(duì)Meissel的算法做了推廣，使其可以計(jì)算N以下的質(zhì)數(shù)和。首先我們對(duì)Meissel的算法做一個(gè)簡(jiǎn)單介紹：
定義
?表示?
中恰好擁有?
個(gè)素因子，且這
?個(gè)素因子
?均大于
?的數(shù)的個(gè)數(shù)，則我們有：
這個(gè)公式我們可以這么理解：?
表示?
中其最小素因子都大于
?的數(shù)的個(gè)數(shù)，這些數(shù)里面包括只有一個(gè)大于?
的素因子的數(shù)，實(shí)際上也就是大于
?的素?cái)?shù)；也包括恰好有兩個(gè)素素因子且這兩個(gè)素因子都大于
?，也包括恰好有三個(gè)素素因子且這三個(gè)素因子都大于
?，依次類推以至無(wú)窮就可以得到所有其最小素因子都大于
?的數(shù)的個(gè)數(shù)，也就是
?。我們定義?
，而
?表示?
中大于
?的素?cái)?shù)的個(gè)數(shù)，則
?，據(jù)此我們展開上式有：
通過(guò)適當(dāng)?shù)倪x擇
?的數(shù)值，我們可以讓
?及以后的項(xiàng)變?yōu)榱?。如我們選擇
?，則有
?，此時(shí)
?及以后的變?yōu)榱?#xff0c;上式變成之前提到的勒讓德的公式，證明勒讓德公式只是這個(gè)公式的一個(gè)特例。如我們選擇
?，則有?
，此時(shí)
?及以后的項(xiàng)變?yōu)榱?。一般?#xff0c;選擇
?，則有?
而
?。假設(shè)我們選擇
?，則有：
經(jīng)過(guò)不太復(fù)雜的推導(dǎo)，可以發(fā)現(xiàn)
?可通過(guò)下式計(jì)算：
其中
?，據(jù)此我們可以計(jì)算?
。使用和上面的類似的原理，并定義
?為區(qū)間?
中恰好有兩個(gè)素因子，且兩個(gè)素因子均大于?
的數(shù)的和，則有：
其中
?，且：
綜合上面兩個(gè)公式，我們也可以計(jì)算
?。這個(gè)算法相對(duì)于勒讓得算法的最顯著的優(yōu)勢(shì)是需要遞歸的次數(shù)更少，如當(dāng)
?時(shí)，
?，因此最大遞歸深度只有168層。但在我自己實(shí)現(xiàn)這個(gè)算法時(shí)，它的表現(xiàn)并沒(méi)有比勒讓得算法更優(yōu)，我猜測(cè)原因是計(jì)算?
時(shí)消耗了過(guò)多資源，不過(guò)也有可能是我自己算法實(shí)現(xiàn)的原因。如果大家有提升這個(gè)算法的方法，還請(qǐng)指出。這個(gè)算法的代碼實(shí)現(xiàn)如下：
def meissel(n=2e6):
primes = list(primerange(1,int(n**(1/2))+1))
cr_primes = [x for x in primes if x
def prime_sum(n):
ps = list(primerange(1,n+1))
return sum(ps)
@lru_cache(maxsize=32)
def sigma(x,a):
if a == 1:
return (x//2)**2 if x%2==0 else (x//2+1)**2
else:
return sigma(x,a-1) - primes[a-1]*sigma(x//primes[a-1],a-1)
def total(x,a):
res,index = 0,a
for p in primes[a:]:
res += p * (prime_sum(x//p) - sum(primes[:index]))
index += 1
return res
a = len(cr_primes)
ans = sigma(n,a) + sum(cr_primes) - total(n,a) - 1
return ans
經(jīng)過(guò)嘗試，至少到我寫這篇文章為止，我自己并沒(méi)有能夠?qū)崿F(xiàn)一個(gè)在效率表現(xiàn)上和處理大規(guī)模問(wèn)題上比Hedgehog算法更優(yōu)的算法。但這種嘗試仍是有意義的，至少可以讓我更加清楚的理解Hedgehog算法的原理，并且對(duì)質(zhì)數(shù)計(jì)數(shù)的各種算法和推廣加深了了解。我相信這些算法仍有優(yōu)化的空間，如果找到的話我再來(lái)做補(bǔ)充。
五、延伸閱讀
前面已經(jīng)提到，質(zhì)數(shù)計(jì)數(shù)是數(shù)論中一個(gè)非常重要的問(wèn)題，既有使用解析數(shù)論等方法對(duì)質(zhì)數(shù)整體分布規(guī)律的研究，也有各種不斷改進(jìn)的計(jì)算
?的確切值的算法。在以上我提到的Meissel算法之后約半個(gè)世紀(jì)，Lehmer[5]對(duì)這個(gè)算法進(jìn)行了進(jìn)一步改進(jìn)，他進(jìn)一步計(jì)算了
?，并使用IBM 701計(jì)算機(jī)計(jì)算了
?，他的計(jì)算結(jié)果只比正確結(jié)果大一，以上從勒讓德到Lehmer的算法實(shí)質(zhì)都是對(duì)勒讓德最初提出算法的某種改進(jìn)，統(tǒng)稱為計(jì)算
?的組合方法(Combinatorial method)。之后在1987年，Lagarias and Odlyzko[4]提出了一種從從解析數(shù)論角度計(jì)算
?的方法，算法中需要用到黎曼Zeta函數(shù)的某些性質(zhì)，并采用數(shù)值積分的方法，這種方法被稱為計(jì)算?的分析方法(見(jiàn)參考文獻(xiàn)[1])，這個(gè)算法雖然具備更好的漸近性，但在性能上比不上作者們?cè)?985年提出的對(duì)Meissel-Lehmer算法的改進(jìn)(見(jiàn)[3])。上面幾種算法的詳細(xì)的時(shí)間與空間復(fù)雜度分析可以參見(jiàn)這篇文章，這里列一個(gè)簡(jiǎn)要的結(jié)果：
在此之后，Deleglise-Rivat以及Xavier Gourdon又對(duì)算法做出了改進(jìn)。在github上作者Kim Walisch對(duì)以上算法做了實(shí)現(xiàn)，他的測(cè)試結(jié)果如下：
在2015年9月，他宣布利用自己的算法計(jì)算了
?，計(jì)算花費(fèi)了數(shù)年時(shí)間，最高峰時(shí)使用了235G的內(nèi)存，之后他們又花了五個(gè)月時(shí)間進(jìn)行重新計(jì)算驗(yàn)證，確認(rèn)的結(jié)果是：
這是目前維基頁(yè)面上列出的最大的
?值，至于是否有人算出了更大的?
值，我沒(méi)有查到確切的信息。
以上計(jì)算?的算法中自Lehmer以后都變得非常復(fù)雜，至少我已經(jīng)無(wú)法理解。同時(shí)由于使用的方法越來(lái)越復(fù)雜，其代碼實(shí)現(xiàn)也會(huì)變得更加麻煩。而且相關(guān)方法能否進(jìn)行推廣用來(lái)計(jì)算N以下的質(zhì)數(shù)和也未可知，這些問(wèn)題感興趣的同學(xué)可以繼續(xù)探索。
最后，參考文獻(xiàn)[7]，設(shè)
?，則
?以下質(zhì)數(shù)的和的漸進(jìn)估計(jì)是：
全文完。
六、參考文獻(xiàn)Crandall, R., & Pomerance, C. B. (2006). Prime numbers: a computational perspective (Vol. 182). Springer Science & Business Media.
Deléglise, M., & Rivat, J. (1996). Computing ( ): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method. Mathematics of Computation of the American Mathematical Society, 65(213), 235-245.
Lagarias, J. C., Miller, V. S., & Odlyzko, A. M. (1985). Computing ( ): the Meissel-Lehmer method. Mathematics of Computation, 44(170), 537-560.
Lagarias, J. C., & Odlyzko, A. M. (1987). Computing π (x): An analytic method. Journal of Algorithms, 8(2), 173-191.
Lehmer, D. H. (1959). On the exact number of primes less than a given limit. Illinois Journal of Mathematics, 3(3), 381-388.
Riesel, H. (2012). Prime numbers and computer methods for factorization (Vol. 126). Springer Science & Business Media.
Sinha, N. K. (2010). On the asymptotic expansion of the sum of the first n primes. arXiv preprint arXiv:1011.1667.
Xavier Gourdon, Computation of pi(x) : improvements to the Meissel, Lehmer, Lagarias, Miller, Odllyzko, Deléglise and Rivat method, February 15, 2001.
總結(jié)
以上是生活随笔為你收集整理的java循环1000000000_求十亿内所有质数的和，怎么做最快?的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： PyQt特殊对话框介绍
- 下一篇： c语言sizeof测量字符组长度,C语言