要尋找質數，埃拉托斯特尼篩法是個很好的方法。此外，印度人 M. Arrayal 、N. Kayla 以及 N. Saxena 提出了 AKS 質數檢驗演算法也不錯，它能同時證明某範圍內所有質數。
步驟一：考慮以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
步驟二：標出序列中的第一個質數，數列變成：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
步驟三：將剩下數列中，將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
步驟四：若該數列的最大值小於第一個質數的平方，那麼剩下的數列中所有的數都是質數，否則返回步驟二。本例中，由於25大於2的平方，我們返回步驟二。
剩下的序列中第一個質數是3，將主序列中3的倍數劃掉（以灰色表示），該數列變成：
2 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。但25仍大於3的平方，我們返回步驟二。
現在序列中第一個質數是5，同樣將序列中5的倍數划出，主序列成了：
2 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 。 因為25等於5的平方，步驟完成。結論：去掉紅色的數字，2到25之間的質數是：2 3 5 7 11 13 17 19 23。
參考資料：有趣的數、數的性質、談談質數
沒有留言:
發佈留言