数学研发论坛

 找回密码
 欢迎注册
查看: 1363|回复: 17

[求助] Prime函数的逆函数是什么函数?

[复制链接]
发表于 2019-2-15 16:40:46 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 mathematica 于 2019-2-15 16:43 编辑

用mathematica软件,
求第1个素数就用Prime[1]
求第2个素数就用Prime[2]
求第10个素数就用Prime[10]
但是有时候我知道某一个素数,比如257,我想反过来求是第几个,应该如何解决呢?

比如求193707721是第几个素数,
我是这样求的
  1. Clear["Global`*"];
  2. s=FactorInteger[2^67-1][[1,1]](*需要被判定的素数*)
  3. (*先求出下界与上界*)
  4. a=IntegerPart[n/.FindRoot[193707721==n*(Log[n]+Log[Log[n]]-0),{n,10000},WorkingPrecision->30]]
  5. b=IntegerPart[n/.FindRoot[193707721==n*(Log[n]+Log[Log[n]]-1),{n,10000},WorkingPrecision->30]]+1
  6. (*用二分法求得是第多少个素数*)
  7. Do[
  8.     c=IntegerPart[(a+b)/2];
  9.     pc=Prime[c];
  10.     If[pc<s,a=c,b=c];
  11.     If[pc==s,Print[{c,pc}];Break[]],
  12.     {k,1,5000}
  13. ]
复制代码

运行结果

193707721

10236692

10775121

{10749692,193707721}
所以193707721是第10749692个素数,我好奇软件是如何快速求解出第10749692个素数的.
循环16次,找到这个结果,要是有现成的逆函数就好了

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-2-15 16:42:12 | 显示全部楼层
关于第n个素数的近似公式见维基百科
https://en.wikipedia.org/wiki/Prime_number_theorem
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-15 16:59:35 | 显示全部楼层
你要的就是素数计数函数,大名鼎鼎的$pi(x)$, https://en.wikipedia.org/wiki/Prime-counting_function

点评

但是我感觉这个计数函数有什么快速的计算方法,mathematica一下子就算出来了,不像是穷举弄出来的  发表于 2019-2-16 08:43
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-15 17:03:16 | 显示全部楼层
不大于x的素数个数 PrimePi[x]

点评

顶!  发表于 2019-2-16 08:42
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-2-16 08:43:36 | 显示全部楼层
lsr314 发表于 2019-2-15 17:03
不大于x的素数个数 PrimePi[x]

但是我感觉这个计数函数有什么快速的计算方法,mathematica一下子就算出来了,不像是穷举弄出来的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-16 09:20:48 来自手机 | 显示全部楼层
这个问题你不是第一次问了,本论坛上也已经回答过了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-2-16 09:52:05 | 显示全部楼层
本帖最后由 mathematica 于 2019-2-16 09:55 编辑
mathe 发表于 2019-2-16 09:20
这个问题你不是第一次问了,本论坛上也已经回答过了


你肯定记错了,我第一次问
我自己查到了
Lagarias Miller Odlyzko 算法


https://www.zhihu.com/question/24942373
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-2-16 10:21:52 | 显示全部楼层

  1. Clear["Global`*"];
  2. n=FactorInteger[2^67-1][[1,1]]
  3. a=IntegerPart@LogIntegral[n]
  4. b=PrimePi[n]
  5. N[(a-b)/b,10]
复制代码


193707721
10750500
10749692
0.00007516494426
还是这个对数积分牛

点评

下次估计素数的个数的时候,我就用对数积分  发表于 2019-2-16 10:32
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-16 12:26:34 来自手机 | 显示全部楼层
的确,上一次不是你问的 https://bbs.emath.ac.cn/forum.ph ... id=15604&page=1

点评

果然是我的头像还不够有区分度吗……  发表于 2019-2-16 19:14
修改了  发表于 2019-2-16 15:29
电脑上看不了  发表于 2019-2-16 12:35
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-17 18:03:18 | 显示全部楼层
mathematica 发表于 2019-2-16 10:21
193707721
10750500
10749692

RiemannR[x] 比 LogIntegral[x] 更好
  1. Plot[{RiemannR[x], LogIntegral[x], PrimePi[x]}, {x, 1, 100}]
复制代码

点评

老同志居然也知道RiemannR函数  发表于 2019-2-19 12:16
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-11-19 13:34 , Processed in 0.091781 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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