数学研发论坛

 找回密码
 欢迎注册
查看: 103|回复: 4

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

[复制链接]
发表于 2018-11-30 22:05:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 .·.·. 于 2018-11-30 22:06 编辑

翻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]$
画风相当清奇
但显然这不是我们想要的公式
……
所以
这个快速算法到底是什么
以及,有没有什么比较好的关键词或者网站,用来搜寻这种算法呢?
(虽然感觉有九成概率我就算拿到算法也什么都看不懂)
(万一呢)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-12-1 09:08:46 来自手机 | 显示全部楼层
本质上就是素数计数函数的计算,这个有O(n^(1/3))的算法
Prime-counting_function
有了这个算法后,本题就可以二分法了

点评

好神奇的方法! 我之前想到的是,预先计算出一系列pi(x),然后用伪素数判定公式计算精确的pi(x)的值…… 果然数论比我想象得精妙得多:)  发表于 2018-12-1 14:03
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-12-1 11:20:58 | 显示全部楼层
对于较大的n, 好像用的是个数计算的近似公式,再加上素数判定算法
这两个网站互相印证了:
Prime_number_theorem#Approximations_for_the_nth_prime_number
https://primes.utm.edu/nthprime/algorithm.php
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-12-1 11:25:41 | 显示全部楼层
然后随便敲一个较大的数,让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}
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-12-11 04:17 , Processed in 0.049738 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表