如何有效寻找素数？

　　作者：刘建亚

　　1999年6月1日，人类首次发现超过一百万位的素数。那么，你可知道如何才能寻找到素数呢？

　　取一个正整数x，如何才能找出不超过x的所有素数呢？有一种方法叫作埃拉托色尼筛法，其历史可以上溯到古希腊时期。

　　埃拉托色尼筛法的步骤如下：第一步，列出从2到x的所有整数，保留2，划去所有2的倍数。第二步，在剩余的数列中，紧跟着2的素数是3；保留3，划去所有3的倍数。第三步，在剩余的数列中，紧跟着3的素数是5；保留5，划去所有5的倍数。

　　如此下去，最后一步是，在倒数第二步的剩余数列中，保留最接近且不超过√x的那个素数，划去这个素数的所有倍数。

　　这样，剩下的数列就是不超过x的所有素数。以上做法是基于这样的事实：若x不是素数，则x一定有不大于√x的因子。

　　用埃拉托色尼筛法可以比较方便地编制素数表。要是碰到一个不很大的正整数x（比如不超过10?000），手头刚好没有素数表可查，如何快速地判定它是否是素数呢？事实上，只要拿不大于√x的一切素数去试除x就可以了。

　　关键词：素数

版权所有少年儿童出版社，鼓励任何不用于商业性质的传播