看板 WaKnow
作者 標題 [知識分享]簡單的招數找「質數」
時間 2012年02月24日 Fri. PM 12:17:31
![[圖]](http://waknow.com/wp-content/uploads/2012/02/io9.com_.jpg)
作者：台大邱老師
要把一個小於 1000 的數做因數分解，最原始的試除是可行的。但把 [√1000]=31 以內的質數逐一試除，計算量太大，不用筆算簡直不可能（2、3、5、11這些因數有簡單的判斷法， 但像23、29、31這些質因數，就只能硬除了）。台大邱老師提供一個方法，只要你對 100 以內的數夠熟悉，就可以心算完成這件事喔！厲害吧！
以 667 為例說明這個方法：我們先加上 3 補成十的倍數 680，寫成 667 = 670 – 3。同理，也可以得到
667 = 670 – 3
= 680 – 13
= 690 – 23
= 700 – 33
.
.
.
= 760 – 93
把第一個數除以10，我們發現第三行的兩個數 (69, 23) 有公因數 23，所以立刻可以分解出
667 = (690/23 – 23/23)*23 = 29*23。真快！
這個例子運氣不錯，第 3 組就找到公因數了。如果一直都沒遇到公因數，就要試完十組，試到 (76, 93) 為止，再上去的 (77, 103) 因為出現超過 100 的數，就已經超過我們熟悉的守備範圍了。所以，如果我們得到這十組數字全都互質，就直接判定成質數。這個判定法大部分是對的，除了以下 6 個例外：
403, 533, 697, 713, 731, 793。以上的方法是「往上數」，那麼「往下數」可不可以呢？我們再以 667 為例......
全文http://waknow.com/?p=4296
--
※ 作者: waknow 時間: 2012-02-24 12:17:31
※ 看板: WaKnow 文章推薦值: 0 目前人氣: 0 累積人氣: 476
回列表(←)
分享