[愛數學]簡單的招數找「質數」

[愛數學]簡單的招數找「質數」

io9.com

 
作者:台大邱老師
 
 
要把一個小於 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 為例:

667 = 660 + 7
= 650 + 17
.
.
.
= 580 + 87
= 570 + 97

其中 (580, 87) 有公因數 29,所以也立刻可以分解出 667 = (580/29 + 87/29)*29 = 23*29。讀者可以試試,上面說的6個「往上數」的例外,用「往下數」全都可以很快找到分解!

另外,對於大於 900 的數,「往上數」會直接出現超過 100 的數。例如,971 「往上數」可以得到:
(98, 9), (99, 19), (100, 29), (101, 39), (102, 49), …

所以這時候最好就改成「往下數」,而且都不會有例外喔!再以971為例 ,我們這次「往下數」:

971 = 970 + 1
= 960 + 11
= 950 + 21
.
.
.
= 880 – 91

因為這十組數:(97, 1), (96, 11), (95, 21),…, (88, 91),全都互質,所以將 971 判定為質數。

但是,「往下數」在小於 900 的數字就有很多例外了。所以,我們還是以「往上數」作為分解 1000 以內的數的流程基礎:

  1. 除了上面所列的「往上數」六個例外數字,遇 900 以下的數,「往上數」十組找出公因數進而分解。
  2. 若遇 900 以上的數,和那六個例外數字,則「往下數」十組找出公因數進而分解。

這個方法多練幾次以後,在一分鐘之內心算出答案是完全可行的。學起來以後跟你的朋友炫耀,你也是數學小天才!
 
 
延伸閱讀:如何學好高中數學 ── 一位數學鬼才老師的分享

延伸閱讀:數學公式,先背起來再說