[讨论] 10秒内计算出1亿素数表, 不输出 相关搜索: 素数

无心人

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

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

gxqcn

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

无心人

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

gxqcn

好的，依楼主，俺弃权

liangbch

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

风云剑

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

tprime

我见到最快没有打表的代码,
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秒）

无心人

规定
int prime[6000000]储存素数表
要输出到该表， 从2到最后一个， 一个都不少
初始化前25个， 不再要求筛出来
但后面的必须筛出来， 如果非筛算法也可以， 但不得利用任何除前25素数外的表
代码限C++ 和汇编， 指令集限P4+SSE2，AMD与Intel均能支持的指令
可多输出， 但不得少输出
：）

计时为全计时方式
从main声明变量结束开始计时， 采取最高优先级进程执行， 以计时准确
到程序退出前计时结束并输出计时结果

tprime

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

无心人

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

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