擂台第36期[素数的计算]

yimins

擂台第36期[素数的计算]

题目：素数的计算
级别：初级
说明：
1、计算出小于1亿的所有素数。
2、比比谁的算法速度最快。
3、计算过程不必显示，但是最后要将计算结果存放在一个数组中，并且输出找到的素数的数目以供校对。同时在代码中自行使用TimeGetTime计算总时间，并输出以供比较。
4、只允许使用VB代码，除了计时可以使用TimeGetTime外不允许使用任何API或者内嵌其它语言代码。

补充说明：为了避免某些人钻空子，规定代码中除了2、3两个数字外不允许出现其它素数。(也就是说除了2和3外所有的素数必须通过运算生成)

请参赛者跟贴中只附上可执行文件。定稿后将源代码发到擂台专用信箱：arena@vbgood.com。
文件及源码文件名格式：用户名_第几期_第几组_版本.rar
由于此信箱垃圾邮件太多，请在发信时一定写明主题。而且记得一定要带上附件！

截稿日期：2007.07.30

PS：
本期题目难度有所下降，希望大家能踊跃参与，即使最后不能得到擂主，但是经过自己的思考和动手，编程的能力也会得到提升。
另外，本期题目以前讨论的比较多，网上可能会找到不少现成的代码，但是希望大家还是自己动脑思考，动手编写一下。对算法的解决能力会有较大的提高。

[ 本帖最后由 yimins 于 2007-7-17 08:36 编辑 ]

yidie

纯属凑凑热闹
代码倒是不多，时间好长啊

质数：5761455 个
耗时： 287515 ms

yimins

原帖由 yidie 于 2007-7-16 11:38 发表
纯属凑凑热闹
代码倒是不多，时间好长啊

质数：5761455 个
耗时： 287515 ms

不错，数字正确了。速度可以慢慢优化嘛。

yidie

把循环次数改一下，其他的没什么可改的。
保存素数的数组只能是动态的，总不能改成定长的。
时间短了一点，不过总觉得好长。

acme_pjz

数组虽然是变长的，但是可以用小于N的质数个数的公式来估计：N/ln(N)，这样不用频繁改数组大小。只用算6N+1和6N-1，在循环里可以p=p+2,p=p+4；编译时一定要把所有高级选项都勾上！

难道连CopyMemory都不能用吗？

yidie

谢谢，采用N/ln(N)估计个数，在循环中就不用频繁改变数组大小了，速度应该可以提高很多，我试试。

acme_pjz

怎么都200多秒……

我以前编过一个程序是以510510个数一组来算的，因为510510=2x3x5x7x11x13x17，所以这些数不用考虑，快了一点……

yimins

原帖由 acme_pjz 于 2007-7-16 14:48 发表
数组虽然是变长的，但是可以用小于N的质数个数的公式来估计：N/ln(N)，这样不用频繁改数组大小。只用算6N+1和6N-1，在循环里可以p=p+2,p=p+4；编译时一定要把所有高级选项都勾上！

难道连CopyMemory都不能用吗？

不能，本期主要目的是让大家练习用算法的方式提高速度。请不要往其它方向努力。

PS：像质数个数的估计公式、编译的时候选择高级选项、在循环里用p=p+2,p=p+4等等这些技巧就很好。继续努力。:)

yidie

速度提高很多哦，频繁改变大小花费了大部分时间，接近三分之二。现在只剩下两次改变大小，OK

yimins

原帖由 yidie 于 2007-7-16 15:24 发表
速度提高很多哦，频繁改变大小花费了大部分时间，接近三分之二。现在只剩下两次改变大小，OK

不错，不错！已经提高一倍有多了！恭喜一下，继续努力！