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[10^7] // Length // AbsoluteTiming要快，
参考了Matlab函数primes的算法，但比matlab的快点

primes[n_] := Block[{p = Range[1, n, 2]},
p[[1]] = 2;
Do[If[p[[(k + 1)/2]] != 0, p[[1/2 (k^2 + 1) ;; ;; k]] = 0], {k, 3, n^.5, 2}];
SparseArray[p]["NonzeroValues"]
];
primes[10^8] // Length // AbsoluteTiming

复制代码

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

[讨论] 10秒内计算出1亿素数表, 不输出