论坛 › 编程擂台 › 10秒内计算出1亿素数表, 不输出

qianyb 发表于 2011-6-2 12:34:42

那个GlobalAlloc函数以前没用过，置0的速度比memset函数的速度快吗？

G-Spider 发表于 2011-6-2 13:13:25

置0的速度不会比memset函数的速度快。windows下可以试试 VirtualAlloc .
GlobalAlloc基本上淘汰了。

tprime 发表于 2011-6-12 20:53:52

98# liangbch


这个算法有点老了， 新的改进算法
"Computation of pitable(x): Improvement to THE MEISSEL, LEHMER, LAGARIAS,
MILLER, ODLYZKO METHOD Deleglise and Rivat method
用这个算法实现我的pi程序, 实现有点粗糙， 还有非常大的优化余地，
自我感觉1秒计算PI（1e12）是可行的。

pi(1e10) = 455052511, time use 125 ms
pi(1e11) = 4118054813, time use 1102 ms
pi(1e12) = 37607912018, time use 11349 ms

liangbch 发表于 2011-6-13 11:18:36

不知道楼上看的是不是这个
http://en.wikipedia.org/wiki/Prime-counting_function

fly 发表于 2011-6-14 22:02:32

我是不行的了。
不过如果是用巨型计算机来实现，算不算作弊？

fly 发表于 2011-6-15 10:09:22

在GMP下如果实现呢？

knate 发表于 2012-6-18 15:20:32

原来这么早就有讨论这玩意了,记录下!

云梦 发表于 2012-6-28 20:00:18

圆周率314159是素数，圆周率100000000位内含有多少素数？（从314159........）
31415926535897932384626433832795028841也是素数。

无心人 发表于 2013-11-25 21:05:59

我去看了看Atkin筛的原理，咋感觉不如咱这里讨论的分块筛法呢？

chyanog 发表于 2013-11-25 22:18:26

本帖最后由 chyanog 于 2013-11-25 22:22 编辑

Mathematica用筛法求10^8以内的素数 4s （CPU 2.1GHZ），比Prime@Range@PrimePi // Length // AbsoluteTiming要快，
参考了Matlab函数primes的算法，但比matlab的快点



primes := Block[{p = Range},
   p[] = 2;
   Do] != 0, p[] = 0], {k, 3,n^.5, 2}];
   SparseArray["NonzeroValues"]
   ];

primes // Length // AbsoluteTiming

查看完整版本: 10秒内计算出1亿素数表, 不输出