求500000000内的素数
原帖：http://forum.simwe.com/thread-942926-1-1.html下面的题目用mathematica来做似乎是没有一点难度的，但要在128M内存之下完成却也并不太容易，大家试试吧
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
发信人: Polaris (北极), 信区: Program
标题: 挑战一下吧
发信站: BBS_兰大西北望 (2010-07-28 21:10:40 Wed), 站内
题目：求500000000以内的素数。
要求：
1、x86 32位平台的代码
2、内存使用不得超过128M
3、求出个数和内容即可，保存到数组里即可，只需要输出个数，不需要输出其它内容，但
是代码里必须得求出来。
4、比谁的速度更快，越快越好
5、语言不限，汇编也可以 用Forcal＋HugeCalc求解，也不知道对不对？代码：!using["HugeCalc"];
mvar:
t0=sys::clock();
i: a=newhc.nstr["1"].free[],
b=newhc.nstr["500000000"].free[],
i=0, a.NextPrime,
while{LE(a,b),
//printff["\r\n"], a.show[],//执行这句，就输出结果
a.NextPrime,
i++
},
i;
/1000;结果：
i: 26355867
228.922
即：500000000以内的素数为26355867个，耗时228.922秒。内存使用23468K，不到25M。
我的机器配置：Intel Core 2 Duo T5500 1.66G 1G内存。只有一个核在使用，因为cpu使用率为50％。 对生成成片连续素数，用 NextPrime 函数那是相当低效的。
5亿内的数可用DWORD表达，无需大整数，
你可先调用 HugeCalc.h 里的 HugeCalc::GetPrimePi(500000000) 得到总数目，
而后开个临时数组，再调用 HugeCalc::GetPrimeList(...) 即可。
如果因空间限制不好一次性开那大的空间，可以开小点，再分次反复调用 GetPrimeList(...)即可。 1# forcal
在双核intel PD 930上，计算2^31 以内素数需要1.8秒 （amd机器更快）
--------------------------------------------------------------
Count number of primes in range[0, 2^31), version 5.0
Copyright by Huang Yuanbing 2007 - 2010
Compiled by MS/vc++ 1600 on 18:01:40 Jul 24 2010
Cpu arch = Intel, Cpu cores = 2, SSE4_Popcnt = 0
: ASM_X86 = 1, LIANGBCH = 0, THREADS = 2
sieve cache size = 30 * 7 * 11 * 13 * 17 * 4 / 30 = 63 K
--------------------------------------------------------------
[L: List prime number (start) (end/count) (step) (type
b
---------------------start benchmark------------------------
PI(2147483647) = 105097565, time use 1837.47 ms
2e9
PI(2000000000) = 98222287, time use 2.01 ms
e9 2e9
PI = 47374753, time use 3.31 ms
10^9+100 123456
PI = 5949, time use 0.93 ms
k e8
-------------------start find kth prime---------------------
Prime = 2038074743, time use 4.64 ms
L e9 2e9 e8
-----------------start list multi prime---------------------
PI = 4814936, time use 3.19 ms
PI = 4792235, time use 2.54 ms
PI = 4773628, time use 2.30 ms
PI = 4757140, time use 3.13 ms
PI = 4741055, time use 2.57 ms
PI = 4725305, time use 2.34 ms
PI = 4711186, time use 3.24 ms
PI = 4699403, time use 2.76 ms
PI = 4685506, time use 2.45 ms
PI = 4674359, time use 3.36 ms
L e9 2e9 e8 1
-----------------start list multi prime---------------------
PI = 4814936, time use 3.04 ms
PI = 9607171, time use 2.26 ms
PI = 14380799, time use 2.83 ms
PI = 19137939, time use 3.12 ms
PI = 23878994, time use 2.32 ms
PI = 28604299, time use 2.85 ms
PI = 33315485, time use 3.19 ms
PI = 38014888, time use 2.37 ms
PI = 42700394, time use 2.89 ms
PI = 47374753, time use 3.30 ms
L e9 2e9 e8 2
-----------------start list multi prime---------------------
PI(1099999999) = 55662470, time use 1.72 ms
PI(1199999999) = 60454705, time use 0.93 ms
PI(1299999999) = 65228333, time use 1.52 ms
PI(1399999999) = 69985473, time use 1.83 ms
PI(1499999999) = 74726528, time use 0.99 ms
PI(1599999999) = 79451833, time use 1.56 ms
PI(1699999999) = 84163019, time use 1.90 ms
PI(1799999999) = 88862422, time use 1.04 ms
PI(1899999999) = 93547928, time use 1.59 ms
PI(1999999999) = 98222287, time use 1.98 ms 对生成成片连续素数，用 NextPrime 函数那是相当低效的。
5亿内的数可用DWORD表达，无需大整数，
你可先调用 HugeCalc.h 里的 HugeCalc::GetPrimePi(500000000) 得到总数目，
而后开个临时数组，再调用 HugeCalc: ...
gxqcn 发表于 2010-7-30 21:45 http://bbs.emath.ac.cn/images/common/back.gif
恩，已经看到了，等封装好后再试一下。
在双核intel PD 930上，计算2^31 以内素数需要1.8秒 （amd机器更快）
--------------------------------------------------------------
Count number of primes in range[0, 2^31), version 5.0 ...
tprime 发表于 2010-8-1 11:03 http://bbs.emath.ac.cn/images/common/back.gif
也是个很牛的东东，学习了。
页:
[1]