VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 48731|回复: 148

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

[复制链接]
 楼主| 发表于 2007-7-16 09:49:23 | 显示全部楼层 |阅读模式
擂台第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 编辑 ]
发表于 2007-7-16 11:38:27 | 显示全部楼层
纯属凑凑热闹
代码倒是不多,时间好长啊

质数:5761455 个
耗时: 287515 ms

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2007-7-16 11:57:35 | 显示全部楼层
原帖由 yidie 于 2007-7-16 11:38 发表
纯属凑凑热闹
代码倒是不多,时间好长啊

质数:5761455 个
耗时: 287515 ms



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

评分

参与人数 2人气 -1 收起 理由
44670 + 1 乱评分是不对的
hovidelphic -2 伟大的负分版主,请继续禁止账号。

查看全部评分

回复 支持 反对

使用道具 举报

发表于 2007-7-16 12:34:51 | 显示全部楼层
把循环次数改一下,其他的没什么可改的。
保存素数的数组只能是动态的,总不能改成定长的。
时间短了一点,不过总觉得好长。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复 支持 反对

使用道具 举报

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

难道连CopyMemory都不能用吗?
回复 支持 反对

使用道具 举报

发表于 2007-7-16 15:11:22 | 显示全部楼层

回复 #5 acme_pjz 的帖子

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

使用道具 举报

发表于 2007-7-16 15:14:12 | 显示全部楼层
怎么都200多秒……

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

使用道具 举报

 楼主| 发表于 2007-7-16 15:23:35 | 显示全部楼层
原帖由 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等等这些技巧就很好。继续努力。:)

评分

参与人数 2人气 -1 收起 理由
44670 + 1 乱评分是不对的
hovidelphic -2 伟大的负分版主,请继续禁止账号。

查看全部评分

回复 支持 反对

使用道具 举报

发表于 2007-7-16 15:24:31 | 显示全部楼层
速度提高很多哦,频繁改变大小花费了大部分时间,接近三分之二。现在只剩下两次改变大小,OK

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复 支持 反对

使用道具 举报

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


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

评分

参与人数 2人气 -1 收起 理由
44670 + 1 乱评分真的是不对的啊,同学
hovidelphic -2 伟大的负分版主,请继续禁止账号。

查看全部评分

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2022-6-30 23:57

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表