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

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

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

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

×

可以使用的知识是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# 的帖子