想了解一下快速寻找第k个素数的原理是什么

.·.·.

翻Mathematica文档的时候偶然看见的

尽管 Wolfram 语言可能分解不了大整数，但是它常常能检测该整数是否为素数. 此外，Wolfram 语言有一个寻找第 k 个素数的快速方法.

这是Mathematica的结果

1. In[1]:= ClearSystemCache[]; Timing[Prime[1000000000000]]
   
2. Out[1]= {15.3125, 29996224275833}

复制代码

Pari/GP给出了……抱歉Pari/GP超时了

1. 21:41:50> prime(100001000000)
   
2. time = 125 ms.
   
3. %1 = 2760755949043
   
4. 21:41:51> prime(100100000000)
   
5. time = 12,548 ms.
   
6. %2 = 2763592093411
   
7. 21:42:03> prime(100200000000)
   
8. time = 25,109 ms.
   
9. %3 = 2766456741569

复制代码

Mathematica表示我一个顶你仨

1. In[1]:= ClearSystemCache[]; Timing[{Prime[100001000000],Prime[100100000000], Prime[100200000000]}]
   
2. Out[1]= {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]$
画风相当清奇
但显然这不是我们想要的公式
……
所以
这个快速算法到底是什么
以及，有没有什么比较好的关键词或者网站，用来搜寻这种算法呢？
（虽然感觉有九成概率我就算拿到算法也什么都看不懂）
（万一呢）

mathe

本质上就是素数计数函数的计算，这个有O(n^(1/3))的算法
Prime-counting_function
有了这个算法后，本题就可以二分法了

wayne

对于较大的n, 好像用的是个数计算的近似公式，再加上素数判定算法
这两个网站互相印证了：
Prime_number_theorem#Approximations_for_the_nth_prime_number
https://primes.utm.edu/nthprime/algorithm.php

wayne

然后随便敲一个较大的数，让Mathematica去计算，比如10^13 会报错 ：ref/message/Prime/largp， 提示Prime函数的算法实现要求不能超过 $2^42 = 4398046511104 = 4.4*10^12$

我的电脑计算这个最大的素数花了超不多一分钟。

1. In[3]:= Timing[Prime[2^42]]
   
2. Out[3]= {57.4287,138666449011757}

复制代码