10秒内计算出1亿素数表, 不输出

无心人 · 发表于 2008-3-13 08:13:18

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

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

x

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

包括所有计算都要在1G以上CPU上10秒内完成
不包括输出时间, 即计算完成后可抛弃现有结果继续计算新结果
但要保证结果一旦输出后是正确

gxqcn · 发表于 2008-3-13 08:23:08

10秒内计算出1亿素数表，这个目标很容易实现。
即便全部输出，我的程序也可满足要求。请下载：素数生成器

无心人 · 发表于 2008-3-13 08:31:21

那你要不输出小于0.1秒
==================
算了, 你别参与了
你把我发表的若干bit位查找算法
给再提高一下吧
绝对是挑战, 感觉总时间能压缩到10%

gxqcn · 发表于 2008-3-13 08:41:24

好的，依楼主，俺弃权

liangbch · 发表于 2008-3-13 10:51:01

需要源代码吗？是统计素数个数呢？还是确实去筛 1 到一亿之间的素数呢？如果是前者，时间应该可以少很多。

风云剑 · 发表于 2008-3-13 12:38:26

肯定要确实筛出来啦。统计个数，挑战1秒100亿差不多。

tprime · 发表于 2008-3-13 12:58:58

我见到最快没有打表的代码,
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声明变量结束开始计时，采取最高优先级进程执行，以计时准确
到程序退出前计时结束并输出计时结果

tprime · 发表于 2008-3-13 14:40:01

如果用基于console程序, 输出将占据90%以上的时间
我到有个建议, 给定一个测试文件，里面有
10000组测试数据,格式为 beg, end(0 < beg <= end < 2^31)(可以加大)
对于每组数据输出素数个数就可,
至少第一次计算任何人也没办法预先打那么大的表

无心人 · 发表于 2008-3-13 15:28:31

素数个数的算法和筛素数的算法根本上是两个不同的算法
算个数只要很少空间就能运行

我这个题目想考算法和缓存处理
：）

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

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

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

回复 1# 的帖子