埃拉托斯芬筛子

蒋明玉

一个大于1的整数，如果除了它本身和1以外，没有别的因数，这个整数就叫质数。如2、3、5、7、11等都是质数。质数也称素数。质数是自然数的一部分，有趣的是，它却与自然数的个数一样，也有无穷多个。

不过，质数看上去要比自然数少得多。有人统计过：在1到1000之间，有168个质数；在1000到2000之间，有135个质数；在2000到3000之间，有127个质数；而在3000到4000之间，就只有120个质数了。越往后，质数就越稀少。

那么怎样从自然数里把质数给找出来呢？ 公元前3世纪，古希腊数学家埃拉托斯芬发明了一种很有趣的方法。在这里让我们先来听一听他测量地球周长的故事，感受一下这位数学家的高超才智。

埃拉托斯芬生活在亚历山大城里，另有一座城市叫塞尼。每当夏至这一天，阳光都能直接照射到塞尼城中一口枯井的底部，同一时刻，亚历山大城却没有这样的景象。埃拉托斯芬利用这一现象，并用数学的相关知识，推算出地球的周长是39250公里，与实际数值的误差不足1%。这是人类历史上第一次进行这样的测量。联想到在埃拉托斯芬去世1800年后，仍然有人为地球是圆的还是方的而喋喋不休时，人们越发称赞埃拉托斯芬高超的计算能力和惊人的胆识。

同学们，觉得他了不起吧！下面让我们一起来学习这位伟大的数学家发明的有趣的找质数的方法。

他首先把自然数按顺序列成一张数表，然后接照一定的规则，逐个把不是质数的数都划掉，最后就得到了全部的质数。

具体规则如下：

如下图，首先把1划掉，因为1既不是质数也不是合数。接下来的一个数是2，它是最小的质数，应予保留，但2的倍数一定不是质数，应该全都划掉。也就是从2起，每隔1个数就划掉1个数。在剩下的数中，3是第一个未被划掉的数，它是质数，应予保留，但3的倍数一定不是质数，应该全都划掉。也就是从3起，每隔2个数划掉1个数。4已被划掉了，在剩下的数中，5成了第一个未被划掉的数，它是质数，也应予以保留，但5的倍数一定不是质数，应该全都划掉。……这样继续划下去，数表上最后剩下的就全都是质数。

……

当时，埃拉托斯芬常把数表写在涂了白蜡的木板上，遇到需要划去的数，就在那个数的位置上刺1个孔。随着合数逐一被划掉，木板上变得千疮百孔，像是一个神奇的筛子，筛掉了合数，留下了质数。所以，人们将这种求质数的方法叫做埃拉托斯芬筛法。

这种方法是世界上最古老的一种求质数的方法。它的原理挺简单，运用起来也很方便。上面就是一个用埃拉托斯芬筛法得到的50以内的质数表。

同学们，你们也可以试一试，用上面的方法，找出1～100的质数。