谁能求出第100亿个素数

数论爱好者

第100个素数是541， 第1000个素数是7919， 第1万个素数是104729 第1亿个素数是2038074749， 第10亿个素数是22801763489。 π(x)分布可能比较好计算一点，网上一直从10^1算到10^23,死算到底，多费些时间可以算出来。 p（n)素数可能难多了，几个软件配合，多次试算，再加技巧和运气，才可能求得。 第10亿个素数我用20多分钟求得，谁能求出第100亿个素数呢？谁能求出第1000亿个素数呢？

wayne

这么大，你想干啥

G-Spider

求在某个数之后或之前的素数很快，而求第1000亿素数意味着都要求。怎么可能会快到哪去呢。 这里http://bbs.emath.ac.cn/thread-3314-1-1.html mpz_nextprime(r, r); 求得r的下一次素数，赋给r 可能会快一点。

wayne

1# 数论爱好者 第10亿个素数，22801763489， 用1秒钟搞定： http://www.wolframalpha.com/input/?i=prime+10^9+th

风云剑

这什么思路？素素定理先估计一个范围，然后循环nextprime？

数论爱好者

第100亿个素数在2.5204×10^11至2.5208×10^11之间 251624684681起往下算 不易计算，再看看

tprime

我的筛法程序比顶楼的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

tprime

---------------------------------------------------------------- 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

medie2005

252097800623

tprime

[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