谁能求出第100亿个素数

数论爱好者 · 发表于 2011-9-1 16:47:39

第100亿个素数1个小时奋战，终于被找到
第100亿个素数是252097800623，与预测有些不准，说明素数无规律
楼上的算pi（x）与我的p（n）不是一回事
已经算到pi（10^23),而p（10^11）还遥遥无期

风云剑 · 发表于 2011-9-1 16:54:36

他是验证了你的结果。
PI(252097800623) = 10000000000, time use 32.509 s

medie2005 · 发表于 2011-9-1 17:09:28

PI(29996224275833) = 100000000000

tprime · 发表于 2011-9-1 17:16:46

11# 数论爱好者
先用pi(x) 估算范围, 在用筛法计算, 取决于估算准确度

Dusart99
P. Dusart, "The kth prime is greater than k(ln k + ln ln k-1) for k> 2," Math. Comp.,
n (log n + log log n - 1.0073) < p(n) < n (log n + log log n - 0.9385) n > 598
(x/log x)(1 + 0.992/log x) < pi(x) <(x/log x)(1 + 1.2762/log x) x > 598
我的程序可以计算第K个素数, 瓶颈在于pi(x)算法不高效

计算pi(x)高效算法不是筛法, 所以很快. 用筛法计算p(x) 效率太低
还得靠估算范围, 结合pi(x)和筛法

tprime · 发表于 2011-9-1 21:45:59

1# 数论爱好者

Seive Size 不是越大越好，和cpuL1，或L2大小一致性能最好
计算起始小于1e12 用L1 （32 - 64）
大于1e14 用L2 （256 - 1024）

数论爱好者 · 发表于 2011-9-1 22:40:12

本帖最后由数论爱好者于 2011-9-1 22:42 编辑

medie2005发表的PI(29996224275833) = 100000000000怀疑数据不正确
第1000亿个素数的范围应该小于2856036374000

数论爱好者 · 发表于 2011-9-1 22:42:53

本帖最后由数论爱好者于 2011-9-1 22:44 编辑

medie2005发表的PI(29996224275833) = 100000000000怀疑数据不正确
第1000亿个素数的范围应该小于2856036374000

tprime · 发表于 2011-9-1 23:25:48

本帖最后由 tprime 于 2011-9-1 23:29 编辑

p(1e11) = 27e11+60e9+7e8+2e7+7e6+3e5+2e3+4e2 + 19 = 2760727302419
pi(27e11+60e9+7e8+2e7+7e6+3e5+2e3+4e2+19) = 100000000000, time use 14117 ms

这下满意了吧，幸亏以前写的pi（x）程序还能用

数论爱好者 · 发表于 2011-9-1 23:32:44

tprime
我的估计值是2760772795727，比你的稍大了些
谢谢你的计算

数论爱好者 · 发表于 2011-9-2 01:11:49

medie2005发表的PI(29996224275833) = 100000000000怀疑数据不正确
但是一万亿个素数的参考值是2999617527400左右
因此PI(29996224275833) = 100000000000等于号右边可能打少了一个0，若其值正确，则第一万亿个素数已经找到
PI(29996224275833) = 10^12
有能力的验证一下PI(29996224275833)

账号		自动登录	找回密码
密码			欢迎注册

[原创] 谁能求出第100亿个素数