求500000000内的素数

forcal

原帖：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

用Forcal＋HugeCalc求解，也不知道对不对？代码：

1. !using["HugeCalc"];
   
2. mvar:
   
3. t0=sys::clock();
   
4. i: a=newhc[HI].nstr["1"].free[],
   
5.    b=newhc[HI].nstr["500000000"].free[],
   
6.    i=0, a.NextPrime[a],
   
7.    while{LE(a,b),
   
8.      //printff["\r\n"], a.show[],  //执行这句，就输出结果
   
9.      a.NextPrime[a],
   
10.      i++
    
11.    },
    
12.    i;
    
13. [sys::clock()-t0]/1000;

复制代码

结果：
i: 26355867
228.922
即：500000000以内的素数为26355867个，耗时228.922秒。内存使用23468K，不到25M。
我的机器配置：Intel Core 2 Duo T5500 1.66G 1G内存。只有一个核在使用，因为cpu使用率为50％。

gxqcn

对生成成片连续素数，用 NextPrime 函数那是相当低效的。
5亿内的数可用DWORD表达，无需大整数，
你可先调用 HugeCalc.h 里的 HugeCalc::GetPrimePi(500000000) 得到总数目，
而后开个临时数组，再调用 HugeCalc::GetPrimeList(...) 即可。
如果因空间限制不好一次性开那大的空间，可以开小点，再分次反复调用 GetPrimeList(...)  即可。

tprime

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
[MARCO] : ASM_X86 = 1, LIANGBCH = 0, THREADS = 2
sieve cache size = 30 * 7 * 11 * 13 * 17 * 4 / 30 = 63 K
--------------------------------------------------------------

        [H: Help]
        [B: Benchmark]
        [P: Print time]
        [Z: Exit programming]
        [C: Cache of cpu L1 size(16 - 64k)]
        [U: Unit test with prime.pi (cases) (cache) (flag)]
        [F: Save result to prime.pi]
        [T: Threads number (2 - 16)]
        [S: Screen print (start) (end)]
        [K: Kth prime number (n 1 - e8)]
        [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[1000000000, 2000000000] = 47374753, time use 3.31 ms
10^9+100 123456
PI[1000000100, 1000123556] = 5949, time use 0.93 ms
k e8
-------------------start find kth prime---------------------
Prime[100000000] = 2038074743, time use 4.64 ms
L e9 2e9 e8
-----------------start list multi prime---------------------
[1000000000:2000000000:100000000]
PI[1000000000, 1099999999] = 4814936, time use 3.19 ms
PI[1100000000, 1199999999] = 4792235, time use 2.54 ms
PI[1200000000, 1299999999] = 4773628, time use 2.30 ms
PI[1300000000, 1399999999] = 4757140, time use 3.13 ms
PI[1400000000, 1499999999] = 4741055, time use 2.57 ms
PI[1500000000, 1599999999] = 4725305, time use 2.34 ms
PI[1600000000, 1699999999] = 4711186, time use 3.24 ms
PI[1700000000, 1799999999] = 4699403, time use 2.76 ms
PI[1800000000, 1899999999] = 4685506, time use 2.45 ms
PI[1900000000, 1999999999] = 4674359, time use 3.36 ms
L e9 2e9 e8 1
-----------------start list multi prime---------------------
[1000000000:2000000000:100000000]
PI[1000000000, 1099999999] = 4814936, time use 3.04 ms
PI[1000000000, 1199999999] = 9607171, time use 2.26 ms
PI[1000000000, 1299999999] = 14380799, time use 2.83 ms
PI[1000000000, 1399999999] = 19137939, time use 3.12 ms
PI[1000000000, 1499999999] = 23878994, time use 2.32 ms
PI[1000000000, 1599999999] = 28604299, time use 2.85 ms
PI[1000000000, 1699999999] = 33315485, time use 3.19 ms
PI[1000000000, 1799999999] = 38014888, time use 2.37 ms
PI[1000000000, 1899999999] = 42700394, time use 2.89 ms
PI[1000000000, 1999999999] = 47374753, time use 3.30 ms
L e9 2e9 e8 2
-----------------start list multi prime---------------------
[1000000000:2000000000:100000000]
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

forcal

对生成成片连续素数，用 NextPrime 函数那是相当低效的。
5亿内的数可用DWORD表达，无需大整数，
你可先调用 HugeCalc.h 里的 HugeCalc::GetPrimePi(500000000) 得到总数目，
而后开个临时数组，再调用 HugeCalc: ...
gxqcn 发表于 2010-7-30 21:45

恩，已经看到了，等封装好后再试一下。

forcal

在双核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

也是个很牛的东东，学习了。