数学研发论坛

 找回密码
 欢迎注册
查看: 3715|回复: 6

[测试] 求500000000内的素数

[复制链接]
发表于 2010-7-30 19:12:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
原帖: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、语言不限,汇编也可以
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-30 19:14:35 | 显示全部楼层
用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%。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-30 21:45:03 | 显示全部楼层
对生成成片连续素数,用 NextPrime 函数那是相当低效的。
5亿内的数可用DWORD表达,无需大整数,
你可先调用 HugeCalc.h 里的 HugeCalc::GetPrimePi(500000000) 得到总数目,
而后开个临时数组,再调用 HugeCalc::GetPrimeList(...) 即可。
如果因空间限制不好一次性开那大的空间,可以开小点,再分次反复调用 GetPrimeList(...)  即可。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-8-1 11:03:43 | 显示全部楼层
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

PrimeNumber.exe

126 KB, 下载次数: 4, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

统计输出区间素数,第k个素数

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-8-2 12:27:54 | 显示全部楼层
对生成成片连续素数,用 NextPrime 函数那是相当低效的。
5亿内的数可用DWORD表达,无需大整数,
你可先调用 HugeCalc.h 里的 HugeCalc::GetPrimePi(500000000) 得到总数目,
而后开个临时数组,再调用 HugeCalc: ...
gxqcn 发表于 2010-7-30 21:45

恩,已经看到了,等封装好后再试一下。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-8-2 12:31:11 | 显示全部楼层

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

也是个很牛的东东,学习了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-10-23 20:25 , Processed in 0.059627 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表