肉书屋

手机浏览器扫描二维码访问

埃拉托斯尼筛子有多大（第1页）

埃拉托斯尼筛子有多大

由于素数没有规律，所以人们只好用笨办法去数，这种笨办法在公元前二世纪就开始采用了。

当时的古希腊哲学家兼数学家埃拉托斯尼就是用的这种办法。

他把从1至100的一百个自然数排成10×10的方阵，然后根据素数的性质：它除去1和其本身不能被任何其他数整除，所以只要在表中相继除去2的倍数、3的倍数、5的倍数、7的倍数……等等。

显然，这如同用2号筛子、3号筛子、5号筛子等等一次一次过筛，所有合数都给筛走了，剩下的当然是素数了。

由于这种办法，如同过“筛子”

一样，所以历史上称之为“埃拉托斯尼筛法”

。

这种办法能很迅速地筛去许多合数，如4、6、8、10四列数全部筛去，2、5两列从12、15开始也全部筛去。

可以推断，假如这个表往下延伸，使总的自然数达1000，10000或更大，那么这儿列延伸下去也可全部筛去。

由此说明，素数只是在1、3、7、9儿列中存在，如果把方形中11的倍数除去，再把圆圈部分的数除去，剩下的就是1-100之间的所有素数。

这种筛选法虽然说是个笨办法，但笨中有巧。

比如，我们用5去筛的话，它的倍数应该有10、15、20、25、30……等等，但是由于10、15、20三个数已经被2和3的筛子筛去了，已不复存在，所以只需要从25开始过筛。

这说明，用5去筛，只需从52开始进行。

同样，用n去筛，只需从n2以后的数开始进行。

这样就大大简化了工作量。

这个笨办法肯定能使我们找到所有的素数，但肯定又找不完所有的素数。

因为人的生命是有限的，即使采用电子计算机，计算速度可以加快，但也是有限的。

所以，埃拉托斯尼筛法虽然可行，但这个筛子该多大，实在是无法说清。

请关闭浏览器阅读模式后查看本章节，否则将出现无法翻页或章节内容丢失等现象。