1樓：
能跑完的。primecount 的githubhttps://github.com/kimwalisch/primecount
，親測兩秒多
2樓：「已登出」
There are primesunder .
Let and can be then derived using theMbius inversion.Riemanndiscovered that for 1, \frac=\int_^ \pi^(x) }dx" eeimg="1"/>.
By theMellin inversion theoremfor 1)" eeimg="1"/>(see explanations below).
LagariasandOdlyzkosuggest introducing aMellin transform pairand to obtain toforce a convergencewhere x \end\right." eeimg="1"/>. This is ageneralisationof theRiemann's explicit formulaif we let and .
Galwaysuggests and . Let be anantiderivativeof that , then the integral becomes which can be computed using (see explanations below). One may use theseries expansiontointegrateevery term.
You still need anarbitrary-precision arithmetic computationand afast Fourier transform-basedRiemann–Siegel formula(for instance,Odlyzko–Schnhage algorithm) to compute on thecritical linewith theTuring's methodto catch allzeros[1].
TheMellin transformindeed establishes aspecialrelationship between theRiemann prime counting functionand theRiemann zeta-functionasand .
Atime complexityreference has suggested that thebest prime sieverequires in time, which may not suit the problem. Theanalytical methodrequires one to compute at least zeros of theRiemann zeta functionon thecritical linewitharbitrary precision arithmetic, which is usually times slower thanfloating-point arithmetic. Thus, I doubt that the task is impossible in seconds.
List of non-elementary mathematical functions involved in this answer:
: thereal function, returns the real part of a complex number.
: theRiemann zeta-function.
: thecomplementary error function, it isholomorphic.
3樓：Rattry
這裡是題主。
這裡的 10s 預設的運算量級別是 。所以請不要刷 min25 了 ， min25 可以在 10s 內跑過 就已經奇蹟了 , min25 適合隔壁的 而不是這裡的 。(洲閣篩它不香麼?
話說 min25 就是 Hedgehog?)
Meissel 的話也不可能跑過 , 不過有大佬科普一下還是好的 , 畢竟這玩意兒網上也沒有多少資料..
本來看看有沒有大佬可以科普一下 的演算法的 。( 也可以來的鴨)分塊打表是個好方法 , 不過它只能跑 左右 (還要配合大常數的 Miller-rabin) 。
100以上的質數怎麼求？
陳炳好 小於9的質數有 2,3,5,7 計算質數時，首先排除偶數和5結尾的數。2,5 的倍數計算 9 到 48 之間的質數，只需篩去 3 的倍數。計算 49 到 168 只需篩去 3,7,11 倍數計算 169 到 360，篩去 3,7,11,13,17 倍數 計算 361 到 841，篩 3,5,...
所有質數的總和正好等於所有數字的總和嗎？
PIAPIABIA 為啥大家都預設是正整數？難道就沒人定義什麼數字嗎？複數是不是數？四元數是不是數？向量 矩陣 群 環算不算？和是什麼意思？數與數之間一定可以相加嗎運算規律相等嗎？ 卓里奇的數學分析 我覺得要回答這個問題，要涉及幾個概念。一即所有質數和整數之和是啥意思？因為這不是普羅大眾理解的和。二...
如何求第n項質數，其n對應質數的上界和下界？
CWKSC 我是題主，我再補充一下。簡單來講，就是在問 和第項質數之間的關係。lowerLimit 至 upperLimit 意味著查詢範圍，在這個範圍內查詢 等於 越小的範圍可減少運算量。我在這舉乙個例子 下界 lowerLimit 顯然可以是 因為除了 之外，其他質數都不是偶數，或其他質數都是奇...