软件工程

本类阅读TOP10
·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八)： CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

→ 分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
用Eratosthenes筛法查找质数

作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站
这两天服务器不知出了什么乱子，死活log不上去，我急得就像一个看见后院起火、有锁匙却回不了家的人。如果说，涕淌居有什么让我一直牵挂的，就属我的一篇低水平的BG文惹来的争论了。

绝大部分的争论都集中于那个经典算法上。相信很多非计算机科班出身的人都和我一样，看到那段算法第一直觉是不知道它在干什么。我更是冲动而超低水平地对它进行否定，现在真是后悔不迭。我总结了关于筛法的资料，趁着现在涕淌居服务器没挂掉，赶紧发表出来呵呵。目的是为了让更多的人能了解这个算法不至于犯我这样的错误，并向大家保证——今后涕淌居再不会出现这样无聊的文章。

静下心来看看算法真是一件很陶冶情操的事情——尤其是像“筛法”这样简单而经典的算法。“筛法”并不是什么针对计算机的优化算法，它早在两千多年前就被希腊数学家埃拉托斯特尼发现了。它的原理是什么呢？其实非常简单，花三分钟你就能理解。

先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就形象地把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。

你可以看看这幅图，像不像个大筛子？


其实筛法的经典并不仅在于它的构思有多么取巧；在历史上，人们更是间接地籍由筛法证明出了“不存在最大的质数”这个貌似明显的事实。嘿嘿，你能证明一下吗？

相关文章：

相关软件：