找回密码
 欢迎注册
查看: 42474|回复: 24

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

[复制链接]
发表于 2011-9-1 12:13:37 | 显示全部楼层 |阅读模式

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

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

×
第100个素数是541,
第1000个素数是7919,
第1万个素数是104729
第1亿个素数是2038074749,
第10亿个素数是22801763489。
π(x)分布可能比较好计算一点,网上一直从10^1算到10^23,死算到底,多费些时间可以算出来。
p(n)素数可能难多了,几个软件配合,多次试算,再加技巧和运气,才可能求得。
第10亿个素数我用20多分钟求得,谁能求出第100亿个素数呢?谁能求出第1000亿个素数呢?
第10亿个素数.GIF
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 12:28:29 | 显示全部楼层
这么大,你想干啥
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 12:35:31 | 显示全部楼层
求在某个数之后或之前的素数很快,而求第1000亿素数意味着都要求。怎么可能会快到哪去呢。
这里http://bbs.emath.ac.cn/thread-3314-1-1.html
mpz_nextprime(r, r);        求得r的下一次素数,赋给r
可能会快一点。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 12:59:04 | 显示全部楼层
1# 数论爱好者
第10亿个素数,22801763489,
用1秒钟搞定:
http://www.wolframalpha.com/input/?i=prime+10^9+th
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 13:22:32 | 显示全部楼层
这什么思路?素素定理先估计一个范围,然后循环nextprime?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-9-1 13:44:40 | 显示全部楼层
本帖最后由 数论爱好者 于 2011-9-1 14:06 编辑

第100亿个素数在2.5204×10^11至2.5208×10^11之间
251624684681起往下算
不易计算,再看看
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 14:22:48 | 显示全部楼层
本帖最后由 tprime 于 2011-9-1 14:45 编辑

我的筛法程序比顶楼的primesieve(也是ecprime 作者)的略慢10-20%, 在INTEL 新机器上还有点超越.
经过一年精心优化,性能大幅度提升.
计算大起始区间( > 1e16),  < 1e9长度以内我的更快
(初始化比primesieve, ecprime快, 筛法略慢, 整体快点)

如果第二个参数比一个小, 表示计算区间长度,  
1e10  1e9 和 10^10, 10^10 + 10^9是一样的
  
[command or number] : 1e16 10^9
Prime[5761459] = 100000049, save primes to buffer use 38 ms
PI[10000000000000000, 10000001000000000] = 27153205, time use 2210 ms

[command or number] : 1e18 1e9+10^10
Prime[50847538] = 1000000033, save primes to buffer use 446 ms
PI[1000000000000000000, 1000000001000000000] = 24127085, time use 5051 ms

[command or number] : 1 1e10
PI[1, 10000000000] = 455052511, time use 3991 ms

primesieve 还有一个不带UI的程序, 下面对比和我的程序

D:\primesieve\out>primesieve.exe 1e16 -o1e9
START      = 10000000000000000
STOP       = 10000001000000000
Sieve size = 64 Kilobytes
Threads    = 1
Prime numbers : 27153205
Time elapsed  : 2.511 sec

D:\primesieve\out>primesieve.exe 1e18 -o1e9
START      = 1000000000000000000
STOP       = 1000000001000000000
Sieve size = 512 Kilobytes
Threads    = 1
Prime numbers : 24127085
Time elapsed  : 8.268 sec

D:\primesieve\out>primesieve.exe 0 1e10
START      = 0
STOP       = 10000000000
Sieve size = 64 Kilobytes
Threads    = 1
Prime numbers : 455052511
Time elapsed  : 3.115 sec
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 14:36:11 | 显示全部楼层
本帖最后由 tprime 于 2011-9-1 14:38 编辑

----------------------------------------------------------------
Count/Sieve number of primes in range(0, 1E18), version 8.9
Implemented by the segmented sieve of Eratosthenes with wheel = 30
@Copyright by Huang Yuanbing 2007 - 2011 bailuzhou@163.com
----------------------------------------------------------------
----------------------------------------------------------------
Compiled by GNU/g++ 4.6.2 on 14:11:49 Sep  1 2011
Cpu arch = x86, cores = 4, SSE4_Popcnt = 0
[MARCO] : ASM_X86 = 0, LIANGBCH = 0, BUCKET = 1
[MARCO] : OPT_SAVE = 1, MEMBLOCK_SIZE = 32k, PDIFF = 255
pre sieve size = 30 * 7 * 11 * 13 * 17 * 19 * 2 / 30 = 512 K
----------------------------------------------------------------

        [H: Help]
        [B: Benchmark]
        [D: Debug log]
        [P: Print time]
        [G: Progress of calculating]
        [Q: Exit]
        [V: Version]
        [A: Result compare by two algorithm]
        [S: Sieve size (10 - 2048)]
        [C: Cpu L1 data cache size (16, 32, 64, 128, 256)]
        [U: Unit test prime.pi (cases) (cache) (rw flag)]
        [F: Save result to prime.pi]
        [O: Factor of n]
        [T: Threads number (2 - 16)]
        [P: Print prime in [start, end]]
        [K: Kth prime number (n 1 - e8)]
        [L: List (start) (end/count) (step) (type 0 1 2)]


[command or number] : b
---------------------start benchmark------------------------
pi(10^01) = 4
pi(10^02) = 25
pi(10^03) = 168
pi(10^04) = 1229
pi(10^05) = 9592
pi(10^06) = 78498
pi(10^07) = 664579
pi(10^08) = 5761455
pi(10^09) = 50847534
pi(10^10) = 455052511
pi(2^32)  = 203280221
pi(10^12, 10^12+2^32) = 155428406
pi(10^13, 10^13+2^32) = 143482916
pi(10^14, 10^14+2^32) = 133235063
pi(10^15, 10^15+2^32) = 124350420
pi(10^16, 10^16+2^32) = 116578809
pi(10^17, 10^17+2^32) = 109726486
pi(10^18, 10^18+2^32) = 103626726
Timer elapsed 59.90sec
All tests passed SUCCESSFULLY!

[command or number] : 1e18 1e10
Prime[50847538] = 1000000033, save primes to buffer use 433 ms
PI[1e18, 1e18+1e10] = 241272176, time use 27302 ms

[command or number] : 0 1e9
PI(1000000000) = 50847534, time use 281 ms

[command or number] : p 1e18 1e2
-------------------start print prime------------------------
1 1000000000000000003
2 1000000000000000009
3 1000000000000000031
4 1000000000000000079
print prime use 1516 ms

PrimeNumber.exe

52.5 KB, 下载次数: 3, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 15:48:04 | 显示全部楼层
252097800623
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-1 16:23:09 | 显示全部楼层
[input command] : k1 252097800623
Prime numbers
---------start G(n)/PI2(n)/PI(n) -------
thread(2) 8.85%, ~= 31.82 s, Prime numbers ~= 9999936000
thread(1) 17.74%, ~= 31.67 s, Prime numbers ~= 10000068480, err ~= 0.1325%%
thread(3) 26.63%, ~= 31.69 s, Prime numbers ~= 9999665280, err ~= -0.4032%%
thread(2) 35.52%, ~= 31.67 s, Prime numbers ~= 9999866880, err ~= 0.2016%%
thread(2) 44.41%, ~= 31.61 s, Prime numbers ~= 9999924480, err ~= 0.0576%%
thread(4) 53.30%, ~= 31.47 s, Prime numbers ~= 9999987840, err ~= 0.0634%%
thread(3) 62.19%, ~= 31.59 s, Prime numbers ~= 9999826560, err ~= -0.1613%%
thread(3) 71.08%, ~= 31.77 s, Prime numbers ~= 9999866880, err ~= 0.0403%%
thread(4) 79.97%, ~= 31.70 s, Prime numbers ~= 9999970560, err ~= 0.1037%%
thread(3) 88.85%, ~= 31.77 s, Prime numbers ~= 9999849600, err ~= -0.1210%%
thread(1) 97.74%, ~= 31.75 s, Prime numbers ~= 10000039680, err ~= 0.1901%%
PI(252097800623) = 10000000000, time use 32.509 s

[input command] : k1 1e10
Prime numbers
---------start G(n)/PI2(n)/PI(n) -------
thread(2) 8.85%, ~= 1.24 s, Prime numbers ~= 455109120
thread(1) 17.74%, ~= 1.25 s, Prime numbers ~= 455212800, err ~= 2.2781%%
thread(2) 26.63%, ~= 1.22 s, Prime numbers ~= 455040000, err ~= -3.7960%%
thread(2) 35.52%, ~= 1.22 s, Prime numbers ~= 455063040, err ~= 0.5063%%
thread(3) 44.41%, ~= 1.21 s, Prime numbers ~= 455034240, err ~= -0.6329%%
thread(1) 53.30%, ~= 1.23 s, Prime numbers ~= 455091840, err ~= 1.2658%%
thread(4) 62.19%, ~= 1.21 s, Prime numbers ~= 455011200, err ~= -1.7720%%
thread(3) 71.08%, ~= 1.21 s, Prime numbers ~= 455028480, err ~= 0.3798%%
thread(4) 79.97%, ~= 1.21 s, Prime numbers ~= 455011200, err ~= -0.3798%%
thread(4) 88.85%, ~= 1.21 s, Prime numbers ~= 455011200, err ~= 0.0000%%
thread(2) 97.74%, ~= 1.22 s, Prime numbers ~= 455080320, err ~= 1.5191%%
PI(10000000000) = 455052511, time use 1257.89 ms
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 09:56 , Processed in 0.096462 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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