找回密码
 欢迎注册
查看: 124559|回复: 113

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

[复制链接]
发表于 2008-3-13 08:13:18 | 显示全部楼层 |阅读模式

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

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

×
精华
可以使用的知识是100以内素数表
其他都要运算生成

包括所有计算都要在1G以上CPU上10秒内完成
不包括输出时间, 即计算完成后可抛弃现有结果继续计算新结果
但要保证结果一旦输出后是正确
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-13 08:23:08 | 显示全部楼层
10秒内计算出1亿素数表,这个目标很容易实现。
即便全部输出,我的程序也可满足要求。请下载:素数生成器
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-13 08:31:21 | 显示全部楼层
那你要不输出小于0.1秒
==================
算了, 你别参与了
你把我发表的若干bit位查找算法
给再提高一下吧
绝对是挑战, 感觉总时间能压缩到10%
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-13 08:41:24 | 显示全部楼层
好的,依楼主,俺弃权
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-13 10:51:01 | 显示全部楼层
需要源代码吗?是统计素数个数呢?还是确实去筛 1 到 一亿 之间的素数呢?如果是前者,时间应该可以少很多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-13 12:38:26 | 显示全部楼层
肯定要确实筛出来啦。统计个数,挑战1秒100亿差不多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-13 12:58:58 | 显示全部楼层

回复 1# 的帖子

我见到最快没有打表的代码,
http://www.primzahlen.de/files/referent/kw/ecprime.source.zip
在我的AMD3600+ 单线程测试结果 (2.0G) PI(2^31)   0.9s,
我自己写的代码双线程要1.6s
不仅仅是素数统计个数,必须筛选出位数组
(否则有O(n^2/3)/ O(ln(n))的算法,10000亿 PI(x) 就1秒)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-13 13:52:01 | 显示全部楼层
规定
int prime[6000000]储存素数表
要输出到该表, 从2到最后一个, 一个都不少
初始化前25个, 不再要求筛出来
但后面的必须筛出来, 如果非筛算法也可以, 但不得利用任何除前25素数外的表
代码限C++ 和汇编, 指令集限P4+SSE2,AMD与Intel均能支持的指令
可多输出, 但不得少输出
:)

计时为全计时方式
从main声明变量结束开始计时, 采取最高优先级进程执行, 以计时准确
到程序退出前计时结束并输出计时结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-13 14:40:01 | 显示全部楼层
如果用基于console程序, 输出将占据90%以上的时间
我到有个建议, 给定一个测试文件,里面有
10000组测试数据,格式为 beg, end(0 < beg <= end < 2^31)(可以加大)
对于每组数据输出素数个数就可,
至少第一次计算任何人也没办法预先打那么大的表

PrimeNumber70.exe

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

计算PI(beg, end)

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-13 15:28:31 | 显示全部楼层
素数个数的算法和筛素数的算法根本上是两个不同的算法
算个数只要很少空间就能运行

我这个题目想考算法和缓存处理
:)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 13:28 , Processed in 0.050723 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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