埃拉托斯芬篩子

蔣明玉

一個大于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的質數。