2007/02/04

學生眼中的質數檢驗

[撰文:KCY]

要尋找質數,埃拉托斯特尼篩法是個很好的方法。此外,印度人 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

我們得到的質數有:23。但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

參考資料:有趣的數數的性質談談質數

沒有留言: