選單

古希臘數學家埃拉託斯色尼教我們如何篩選質數的方法

古希臘數學家埃拉託斯色尼教我們如何篩選質數的方法

在2200年前,古希臘亞歷山大城市裡,生活著一個知識淵博的學者,在他年邁後雙眼失明,再也無法進行學習和研究,他覺得失去了生命存在的意義,絕食而死。

這不是一個虛構的故事,而是真實地在歷史上存在著。編者,一個碌碌無為的鹹魚,看到這個數學家的故事時,久久無語。

這個老人就是我要介紹的數學家——埃拉托色尼。

埃拉托色尼,Eratothenes,出生於公元前275,出生於古希臘昔蘭尼(今利比亞),是一位偉大的數學家,哲學家,天文學家和地理學家,曾經做過亞歷山大里亞圖書館館長,據說和阿基米德私交不錯。

亞歷山大里亞圖書館是當時西方世界最高的科學和知識中心,能擔任館長的都是德高望重,眾望所歸的學者。

他的主要成就在天文學和地理學,被西方地理學家稱呼為“地理學之父”,因為他第一次創造了“地理學”這個詞彙,替代“地方誌”這個傳統說法。他的著作有《地球大小的修正》和《地理學概論》,可惜都失傳了,後世人只能透過其他作者的引文來了解。

他是歷史上第一次測量地球的周長,大概4萬公里,和實際周長4。0076萬公里相差無幾,他還計算出太陽和地球之間的距離1。47億公里,和實際的距離1。49億公里也很接近。(打字的時候,編者都不敢相信這是真的)

既然要介紹的是數學家,下面就說說他在數學上的成就。

現在有一個以他名字命名的篩選素數的方法,埃拉托色尼篩選法,簡稱埃氏篩或愛氏篩。

素數,需要介紹嗎?素數還有個稱呼就是質數。小學5年級學習的知識。

埃拉託斯色尼篩選法:要想得到一個自然數n以內的全部素數,必須把不大於根號n的所有素數的倍數剔除,其他剩餘的都是。

舉數字100做例子。

第一步:100開平方根得到10,

第二步:求1~10之間的素數有2,3,5,7,

第三步:從1~100·把2,3,5,7的倍數地數去掉,

剩餘的其他數都是素數。

我用顏色標了圖,把2選定為素數顏色紅色,再把2的倍數標為綠,去掉,再去掉3的倍數藍色,5的倍數黃色,7的倍數紫色,剩下的就是素數,我全部塗成紅色了。

古希臘數學家埃拉託斯色尼教我們如何篩選質數的方法

同樣的,我們可以算1萬的素數,第一步1萬開平方根等於100,然後得出100以內的素數25個,然後去除這25個素數的所有倍數,就得到1萬以內所有的素數了。計算機跑起來很快的。

同樣的,計算1億以內的素數,那就1億開平方,得到1萬,計算1萬以內的所有素數,再從1億個數里把這些素數的倍數全部去除掉就可以了。算1萬以內的素數,就是求1萬的開方……這個過程上面寫了,不贅述了。

這個方法還有另外一個用途,常常應用在判斷一個數是不是素。

例如:967是不是質數呢?

那我們先把967開平方,約為31。1,那我們可以找31以內的素數,那就是2,3,5,7,11,13,19,23,29,31。問題就變成判斷967是不是這幾個數的倍數,而不用思考其他的。

這個方法第三個用途,可以應用在因式分解上,判斷一個數是合數後,很容易知道他是哪幾個素數的倍數。

這個和歐幾里德的碾轉相除法求最大公約數,都是極其具有實用價值的方法。

大家可以動動腦筋想想,還有沒有其他的用途?

科普數學·一個數學家一個公式·泰勒斯·泰勒斯定理 科普數學·一個數學家一本書·歐幾里德·幾何原本 科普數學家:阿基米德 發現黃金比例,解決歷史上第一次數學危機的古希臘數學家歐多克斯 科普數學·一個數學家一個公式·畢達哥拉斯·勾股定理 期末考完神獸寫的科普我國數學家——祖沖之 占星大師,天文學大師,繪圖專家,托勒密最愛數學家的頭銜 科普數學家之阿波羅尼奧斯之《圓錐曲線論》 古希臘數學家丟番圖墓誌銘,傳世之作《算術》,讓我們學的頭疼 曾被亞里士多德批評的數學家,被世界誤解兩千多年,直到量子論的 比哥白尼早1800年提出日心說的數學家是誰?阿里斯塔克