極速測試兩位質數

• 27/05/2015

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

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

$$n=a \times b$$

那麼 ab 無可能同時是兩位數,否則 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 整除

標籤: , ,

分類: 代數及百分數

與你的 Facebook 好友分享

發表回應

回應內容: