極速測試兩位質數

一個兩位數，只要測試它可否被 3 或 7 整除，便可判斷它是否質數。

假設 n 是兩位正整數 two digit positive integer，並且是合成數 composite number。那麼 n 必定可寫成由兩個正整數相乘，即是

那麼 a 和 b 無可能同時是兩位數，否則 a×b ≥ 100。換句話說， n 至少有一個質因子 prime factor 是個位數。

用最淺白的說話去解釋，如果把 n 除 2,3,4,…,9 後，所有結果都是小數，n 必定是質數 prime number。

再用例子說明，假設我們要判斷 73 是否質數，只須測試它可否被 2,3,4…,9 所整除。

73 ÷ 2 = 36.5
73 ÷ 3 = 24.3
73 ÷ 4 = 18.25
73 ÷ 5 = 14.6
73 ÷ 6 = 12.2
73 ÷ 7 = 10.4
73 ÷ 8 = 9.125
73 ÷ 9 = 8.11

做到這裡便可停止，不用再測試可否被 10,11,… 等數字所整除，便可確定 73 是質數。

而這方法仍可再簡化。由於 4,6,8 是 2 的倍數，如果 n 可被這些數字整除，n 亦必定可以被 2 整除，所以可省去。同樣原理，9 是 3 的倍數，同樣可省去。

因此，要測試的個位數只剩下 2,3,5,7。 但由於所有 2 的倍數必定是偶數 even number，所以不需要做任何除法便可確定 n 是否可被 2 整除。相似地，所有 5 的倍數，其個位必定是 0 或 5，同樣可輕易地判斷。

餘下的就只有 3 和 7。總括而言，一個兩位數只要符合以下所有條件，便可確定它是質數。

1) 奇數 odd number
2) 個位不是 5
3) 不可被 3 整除
4) 不可被 7 整除

標籤: prime number, 質數

分類: 代數及百分數