厄拉托塞斯筛选法

来源：百度知道 编辑：UC知道 时间：2024/05/21 13:09:24
百度还不完善啊，很多学习上的问题都没有资源，而一些乱七八糟的问题到处都是。很多课本上的名词在百度百科根本没资料。 悲剧

更多译为"厄拉多斯"
厄拉多塞筛法
西元前250年，希腊数学家、亚历山大图书馆馆长厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。
以1-50为例，2是质数，以2为筛子，留下2并删去2的倍数;2之后未被删去的第一个数是3，它是质数。以3为筛子，留下3并删去3的倍数;3之后未被删去的第一个数是5，它是质数。以5为筛子，留下5并删去5的倍数;5之后未被删去的第一个数是7，它是质数。以7为筛子，留下7并删去7的倍数;7之后未被删去的第一个数是11，它是质数。到此就算完成寻找所有介於1和50之间的质数，因为50的平方根大於7而且小於8. 就是说留下的未被删去的数字就都是质数了.