素数统计.

　　这几天围着素数统计这一题就把我搞蒙了.. 题目是这样的: 输入一个整数n, 输出小于等于n的素数个数..

　　刚开始, 觉得题目挺容易的,, 马上写了一个程序出来, 测试了一下, 结果没错.. 急急忙忙的就提交了,, 后来再把题目仔细看了看,, n的范围是1~二百万.. 时间要求时1s. 我自信的敲入了两百万.. 结果十分钟才把结果蹦出来... 我这么没用啊,,, 时间要求1s,, 我这里是10*60s...

　　忽然看到内存的限制,, 这题是128M, 别的题目都是32M.. 我就想怎么利用这些内存呢~? 蠢主意马上出来了, 把1到两百万之间所有的素数都放在一个数组里,, 不就得了..然后再循环比较程序的效率不需要1毫秒就可以执行完的~! 马上行动. 用刚刚的程序生成了一个数组. 然后加几行代码.. KO了~!

　　哈哈,, 感觉有点自豪, 但是毕竟没用到任何算法所以又感觉不怎么滴的.

　　后来看到一幅图:

   

　　就是上面这幅图,, 忽然来了灵感,, 写了好几次, 终于能够把执行时间控制在180~190毫秒以内了..(其实按现实生活中的时间衡量程序是不好的, 因为每个机子的运算能力都不同.. 这里就没考虑那么多.) 后来在网上看到了几个, 竟然能够把时间控制在110~130毫秒之间..　接下来一个更夸张, 是我爸在网上弄到的一个, 天哪.. 直接把时间压缩到了60~70毫秒.. 高峰时期有一次15毫秒(也不是什么高峰时期, 就是一次偶然执行..把我彻底吓到了... 这网上的人一个比一个厉害..)

　　之前(日志今天中午11点写的, 现在22点45.)我把那个程序再度修改一次,, 天哪,, 惊讶~! 时间缩小到了40几毫秒~! 对自己赞一个... 亲一个~~ 还是不亲自己了(怕晚上睡不着` 就算睡着了也怕梦见怪物. 哎, 还是那句话: 不要迷恋哥, 哥只是个传说..)

评论

2 楼 zqynux 2010-03-16  

kimmking 写道

使用素数测试算法

能够详细的说明一下吗`?

1 楼 kimmking 2010-03-16  

使用素数测试算法