厄拉多塞篩法


質數是只有兩個正因數的正整數(大於1),這兩個正因數就是1和它自己。所以質數不能表示為比它小的數字的乘積。
西元前250年,希臘數學家厄拉多塞(Eeatosthese)想到了一個非常美妙的質數篩法,減少了逐一檢查每個數的的步驟,可以比較簡單的從一大堆數字之中,篩選出質數來,這方法被稱作厄拉多塞篩法(Sieve of Eeatosthese)。
以上表為例,2是質數,以2為篩子,留下2並刪去2的倍數;2之後未被刪去的第一個數是3,它是質數。以3為篩子,留下3並刪去3的倍數;3之後未被刪去的第一個數是5,它是質數。以5為篩子,留下5並刪去5的倍數;5之後未被刪去的第一個數是7,它是質數。以7為篩子,留下7並刪去7的倍數;7之後未被刪去的第一個數是11,它是質數。到此就算完成尋找所有介於1和50之間的質數,因為50的平方根大於7而且小於8,現在表格所剩的數字都是質數。


 

Copyright ©1999-2001昌爸工作坊 all rights reserved