埃拉托色尼的筛法：求素数的高效方法

在所有比1大的整数中，除了1和它本身以外，不再有别的因数，这种整数叫作素数。还可以说成素数只有1和它本身两个约数。早在古希腊，大数学家欧几里得就在他的《几何原本》中证明了素数有无穷多个。人们知道，任何一个正整数都可以分解为素数的乘积，如果不计因数的次序，分解形式是唯一的。这叫作算术基本定理，欧几里得早已证明。

古希腊数学家埃拉托色尼（Eratostheness，前284—前194）是托勒密王朝的希腊数学家、地理学家、历史学家、诗人、天文学家。他的贡献主要是设计出经纬度系统，计算出地球的直径，编排了包含675颗星星的星图，现已经失传。制作那时已知世界的地图，沿尼罗河一直到喀土穆，从不列颠群岛到斯里兰卡、从里海到依索比亚。埃拉托色尼还发明了一种筛法：“要得到不大于某个自然数n的所有素数，只要在2至n中将不大于的素数的倍数全部划去即可。”公元前195年，他失明了，一年后绝食而死在亚历山大港。

埃拉托色尼和助手编排星图，右为斯坦福大学校园的“埃拉托色尼筛法”钢雕

公元前250年埃氏首先发明了素数的“筛法”用于寻找自然数中的素数：先把n个自然数按次序排列起来。1不是素数，也不是合数，要划去。第二个数2是素数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都剔除掉。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直持续下去，从小到大一直到n的开方就会把不超过n的全部合数都筛掉，留下的就是不超过n的全部素数。因为希腊人是把数写在涂蜡的板上，每要划去一个数，就在上面记以小点，寻求素数的工作完毕后，这许多小点就像一个筛子，所以人们就把埃拉托色尼的方法叫作“埃拉托色尼筛”，简称“筛法”。

美国斯坦福大学校园在1999年建立“埃拉托色尼筛法”钢雕，是美国重量级的雕塑家马可·迪·苏维洛（Mark di Suvero）的作品，以纪念他的贡献。

埃拉托色尼筛掉不超过100的合数

通过筛选，我们得知，10以内共4个素数；100以内共25个素数；1 000以内共168个素数；10 000以内共1 229个素数；100 000以内共9 592个素数；1 000 000以内共78 498个素数；10 000 000以内共664 579个素数；100 000 000以内共5 761 455个素数。

素数的出现规律一直困惑着数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。

是否能找到素数的简单公式，这个公式能够一个不漏地产生所有的素数，并且对每个输入的值，此公式产生的结果都是素数？几千年来，历代数学家都希望能找到一个数学公式，把全部素数都表示出来。可以证明，一个整系数多项式P（n），如果不是常数函数的话，不会是一个素数公式。

1772年，欧拉指出二次三项式

f（x）＝x 2＋x＋41(www.xing528.com)

对于x＝0，1，2，…，39，这40个值各给出一个素数。由f（x－1）＝f（－x），可得

f（0）＝f（－1），f（1）＝f（－2），f（2）＝f（－3），…

这就表明，这个二次三项式对于x＝－1，－2，…，－40也产生同样的一些素数。因此，f（x）对于80个相继的整数x＝－40，－39，…，38，39都给出素数数值。其等价命题是：函数

f（x－40）＝x 2－79 x＋1 601

对于x＝0，1，2，…，79，这80个值都给出素数数值。1798年，勒让德也给出过n 2＋n＋41。

20世纪的毕格尔证明，若N＝n 2＋n＋72 491，当n＝0，1，2，…，11 000时都是素数，也只有一万多个。

1963年，人们证明了f（x，y）＝x 2＋y 2＋1对无限多对整数（x，y）给出素数数值。可是，x 2＋y 2＋1不只产生素数数值，也会产生偶数。

国外还有人发现：函数

当x和y都是自然数时，只产生素数值，且给出所有的素数值，并且每个奇素数值正好各取一次。