埃拉托斯特尼发明的”素数筛子’？

埃氏筛

埃氏筛，是埃拉托斯特尼筛法的简称，是由埃及数学家埃拉托斯特尼所提出的一种简单检定素数的一种方法。

大概思路如下：

自然数可分成1、素数、合数这三类，一定范围内的自然数中，哪些数是素数呢？古时候，希腊有位叫做埃拉多染尼的数学家想出了如下办法：当时，他将1000内的自然数依次写在一块硬方格板上，然后用2试除各数，将能被整除的都用刀子剜掉；继2之后再用3来如此而行；3之后再用5来如此而行……这样一直进行到无法进行而为止，最后再剜掉1。于是，剩下的没能被剜掉的数便是1000内的素数。

由于得到的是张像筛子一样的图，所以，人们便将这种方法叫做埃拉多染尼筛法。

具体例子如下：

第一步，列出如下这样以2开头的序列：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第二步，标出序列中的第一个素数，主序列变成：

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第三步，将剩下序列中，第二项开始每隔一项划掉(2的倍数,用红色标出。），主序列变成：

3 5 7 9 11 13 15 17 19 21 23 25

第四步，如果现在这个序列中最大数小于第一个素数的平方，那么剩下的序列中所有的数都是素数，否则返回第二步。

本例中，因为25大于2的平方，我们返回第二步：

剩下的序列中第一个素数是3，将主序列中3的倍数划出（红色），主序列变成：

5 7 11 13 17 19 23 25

我们得到的素数有：2，3。

25仍然大于3的平方，所以我们还要返回第二步：

现在序列中第一个素数是5，同样将序列中5的倍数划出，主序列成了：

7 11 13 17 19 23

我们得到的素数有：2 3 5 。

因为25等于5的平方，跳出循环.

结论：去掉红色的数字，2到25之间的素数是：2 3 5 7 11 13 17 19 23。

只能说明人类的计算能力又有一个新的进步了。

最大的素数很久之前已经被证明了是不存在的：

如果a=p1*p2*...*pn+1不是素数，则肯定能表达成

a=pi[(p1*p2..p(i-1)*p(i+1)*p(i+2)*...*pn+k]这样的形式，

其中k=1/pi要求是整数，但不可能做到。

那既然已经知道这是个无限的数，加上目前也没有找到它的规律，对未来下一个更大的素数的寻找，就只能依靠计算机来算出来的，单凭人脑是无法完成的。

素数的探索

目前，互联网梅森素数大搜索（GIMPS）项目宣布发现第 51 个梅森素数和已知最大的素数：2^82,589,933-1，共有 24,862,048 位。

人类在寻找素数的路上一直未有停下脚步，已经有2300多年了。

那当时科学家们又是怎么样寻找素数的呢？

总的来说，为了研究素数，数学家们将正整数通过素数筛选算法，直至仅剩素数保留下来。在 19 世纪，用试除法来筛选获得了数百万以内的素数列表。

当然，现代计算机可以在不到一秒钟的时间内找出数十亿以内的素数，但所用筛法的核心思想 2000 年来从未改变。

公元前 300 年，亚历山大里亚的数学家欧几里得描述到：“素数是只能用 1 来计数的数。”这意味着素数不能被除了 1 以外的任何小于自身的数整除。并且为了保证整数的唯一分解，数学家们并不把 1 看作素数。

此外，欧几里得还证明了素数的无限性——它们的个数没有穷尽。

公元前 200 左右，古希腊数学家埃拉托斯特尼(Eratosthenes)提出了素数的快速筛选法，这是一种简单且历史久远的筛法，用来找出一定范围内所有的素数。

2~100 范围内进行 2,3,5,7 素数筛选

素数筛法的思路是这样的：首先，留下 2 ，把 2 的倍数都划掉； 2 后面第一个没划去的数是 3 ，留下 3 ，把 3 的倍数都划掉；然后留下 5 ，把 5 的倍数都划掉；再留下 7 ，把 7 的倍数都划掉。如此这般，将最小的四个质数——2，3，5，7——的倍数依次筛掉。此时，下一个未被筛掉 11 的平方已经大于 100，所以停止。这样在 2 到 100 之间的整数只执行这 4 次筛选，最终只留下了素数集合。

从 1 ~ 100 之间的数字中筛除 2, 3, 5 和 7 的倍数，留下就是素数通过 8 次筛选步骤，可以分离出 400 以内的全部素数。通过 168 次筛选，可以分离出 100 万以内的全部素数。这便是埃氏筛法的强大之处。

为素数制表的早期代表人物是英国数学家约翰·佩尔(John Pell)，他致力于将有用的数字制成表格。其研究动力来源于对古希腊数学家丢番图(Diophantos)所提出的古老算术问题的研究热情，还来自于对数学真理进行系统整合的个人追求。由于他的不懈努力，在 18 世纪早期 10 万以内的素数得以广泛传播。截止 1800 年，各种独立的研究项目列出了百万以内的全部素数。

---