想了解一下快速寻找第k个素数的原理是什么
本帖最后由 .·.·. 于 2018-11-30 22:06 编辑翻Mathematica文档的时候偶然看见的尽管 Wolfram 语言可能分解不了大整数，但是它常常能检测该整数是否为素数. 此外，Wolfram 语言有一个寻找第 k 个素数的快速方法. 这是Mathematica的结果In:= ClearSystemCache[]; Timing]
Out= {15.3125, 29996224275833}Pari/GP给出了……抱歉Pari/GP超时了21:41:50> prime(100001000000)
time = 125 ms.
%1 = 2760755949043
21:41:51> prime(100100000000)
time = 12,548 ms.
%2 = 2763592093411
21:42:03> prime(100200000000)
time = 25,109 ms.
%3 = 2766456741569Mathematica表示我一个顶你仨In:= ClearSystemCache[]; Timing[{Prime,Prime, Prime}]
Out= {8.60938, {2760755949043, 2763592093411, 2766456741569}}
很好奇Mathematica的算法是什么
在scholar.google.com上面搜索Nth Prime找到的都是类似On Formulae for the Nth Prime Number的文章
里面很多东西很好玩
比如威尔逊定理，$(p-1)! \equiv 1(\mod p)$
从而$\cos \pi [\frac{(x-1)!-1}x]$只有当x为质数（或1）的时候才返回1，否则返回0
于是$\pi(n)=\sum_{x=2}^n\cos \pi [\frac{(x-1)!-1}x]$
画风相当清奇
但显然这不是我们想要的公式
……
所以
这个快速算法到底是什么
以及，有没有什么比较好的关键词或者网站，用来搜寻这种算法呢？
（虽然感觉有九成概率我就算拿到算法也什么都看不懂）
（万一呢） 本质上就是素数计数函数的计算，这个有O(n^(1/3))的算法
Prime-counting_function
有了这个算法后，本题就可以二分法了 对于较大的n, 好像用的是个数计算的近似公式，再加上素数判定算法
这两个网站互相印证了：
Prime_number_theorem#Approximations_for_the_nth_prime_number
https://primes.utm.edu/nthprime/algorithm.php 然后随便敲一个较大的数，让Mathematica去计算，比如10^13 会报错 ：ref/message/Prime/largp， 提示Prime函数的算法实现要求不能超过 $2^42 = 4398046511104 = 4.4*10^12$
我的电脑计算这个最大的素数花了超不多一分钟。
In:= Timing]
Out= {57.4287,138666449011757}
页:
[1]