什麼是因數計算機?
這個工具能針對任何整數,幫你算出與「整除性」相關的所有資訊:完整的正因數清單、所有的因數對、質因數分解,以及它究竟是質數還是合數。因數分解是算術、代數與數論的核心基本功,而這台計算機會瞬間為你完成繁瑣的試除運算。
如何使用
在「求下列數字的因數:」欄位中輸入一個整數後送出即可。負數也可以接受——計算機會以其絕對值來分解因數,因為按照慣例因數都是正數。若輸入小數,則會四捨五入為最接近的整數。結果區會以質因數分解作為標題重點,下方依序顯示因數個數、完整因數清單與因數對。
公式原理
要找出 \(N\) 的所有因數,其實只需要測試到 \(N\) 的平方根為止的可能除數。對於每一個能整除 \(N\) 的除數 \(i\),\(i\) 與 \(N/i\) 都是因數。這比逐一檢查 1 到 \(N\) 的每個數字快得多。至於質因數分解,則是反覆除以最小的質數(先 2,再 3、5、7……),直到只剩下 1 為止,並記錄下每個質數以及它出現的次數(即指數)。
$$i \le \lfloor \sqrt{N} \rfloor$$$$N = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$$
實例演練:21
21 的平方根約為 4.58,所以我們測試 1、2、3、4。我們會找到 \(21 = 1 \times 21\) 以及 \(21 = 3 \times 7\),因此因數為 1、3、7、21(共四個),因數對為 (1, 21) 與 (3, 7)。將 21 除以 3 得到 7,而 7 是質數,所以 $$21 = 3 \times 7$$由於它擁有超過兩個因數,21 是合數。
更多範例:36、60 與 97
每個範例都使用與計算器相同的方法:以整數除數 \(d\) 測試到 \(\sqrt{N}\),將每個除數與 \(N/d\) 配對,再根據質因數的指數計算因數個數。
範例 1:N = 36(完全平方數)
- \(\sqrt{36} = 6\),因此測試 \(d = 1\) 到 \(6\)。
- 可整除的除數:1、2、3、4、6。(5 不行:\(36 \bmod 5 = 1\)。)
- 因數配對:(1, 36)、(2, 18)、(3, 12)、(4, 9)、(6, 6)。配對 (6, 6) 的因數重複,因為 36 是完全平方數。
- 所有因數:1、2、3、4、6、9、12、18、36。
- 質因數分解:\(36 = 2^{2} \cdot 3^{2}\)。
- 計數:\((2+1)(2+1) = 9\) 個因數,與列表相符。完全平方數的因數個數必為奇數:9。
範例 2:N = 60
- \(\sqrt{60} \approx 7.75\),因此測試 \(d = 1\) 到 \(7\)。
- 可整除的除數:1、2、3、4、5、6。(7 不行:\(60 = 8 \cdot 7 + 4\)。)
- 因數配對:(1, 60)、(2, 30)、(3, 20)、(4, 15)、(5, 12)、(6, 10)。共六組配對。
- 質因數分解:\(60 = 2^{2} \cdot 3^{1} \cdot 5^{1}\)。
- 計數:\((2+1)(1+1)(1+1) = 3 \cdot 2 \cdot 2 = 12\) 個因數,且六組配對 × 2 = 12。
- 所有因數:1、2、3、4、5、6、10、12、15、20、30、60。
範例 3:N = 97(質數)
- \(\sqrt{97} \approx 9.85\),因此只需測試到 9 以內的除數。測試質數 2、3、5、7 就足夠了,因為 9 以內的其他除數都是其中某個質數的倍數。
- \(97 = 48 \cdot 2 + 1\)(餘數 1),\(97 = 32 \cdot 3 + 1\)(餘數 1),\(97 = 19 \cdot 5 + 2\)(餘數 2),\(97 = 13 \cdot 7 + 6\)(餘數 6)。
- 除了 1 以外沒有其他除數能整除 97,因此它唯一的因數配對是 (1, 97)。
- 質因數分解:\(97 = 97^{1}\),因此因數個數為 \((1+1) = 2\)。97 是質數。
質數與整除規則參考
100 以內的 25 個質數
| 範圍 | 質數 |
|---|---|
| 1–25 | 2、3、5、7、11、13、17、19、23 |
| 26–50 | 29、31、37、41、43、47 |
| 51–75 | 53、59、61、67、71、73 |
| 76–100 | 79、83、89、97 |
共 9 + 6 + 6 + 4 = 25 個質數。數字 2 是唯一的偶質數。
整除規則
| 除數 | 規則 | 範例 |
|---|---|---|
| 2 | 末位數字為偶數(0、2、4、6、8) | 418 末位是 8,因此可被 2 整除 |
| 3 | 各位數字之和可被 3 整除 | 123:1+2+3 = 6,因此可被 3 整除 |
| 4 | 末兩位數字所組成的數可被 4 整除 | 516:16 = 4 · 4,因此可被 4 整除 |
| 5 | 末位數字為 0 或 5 | 735 末位是 5 |
| 6 | 同時可被 2 和 3 整除 | 138 是偶數,且 1+3+8 = 12,因此可被 6 整除 |
| 8 | 末三位數字所組成的數可被 8 整除 | 3,128:128 = 16 · 8,因此可被 8 整除 |
| 9 | 各位數字之和可被 9 整除 | 729:7+2+9 = 18,因此可被 9 整除 |
| 10 | 末位數字為 0 | 470 末位是 0 |
| 11 | 奇偶位數字交錯相減的結果可被 11 整除(包括 0) | 2,728:2 − 7 + 2 − 8 = −11,因此可被 11 整除 |
因數用語說明
- 因數(除數)
- 能整除某數且沒有餘數的正整數。4 是 12 的因數,因為 \(12 \bmod 4 = 0\)。
- 倍數
- 某數乘以整數所得的結果。12、24 和 36 都是 12 的倍數。若 \(a\) 是 \(b\) 的因數,則 \(b\) 是 \(a\) 的倍數。
- 因數配對
- 兩個因數的乘積等於該數,例如 60 的 (3, 20)。檢查到 \(\sqrt{N}\) 的除數即可找出所有配對。
- 質數
- 大於 1 且恰好只有兩個正因數(1 與它本身)的整數,例如 2、3、5、97。
- 合數
- 大於 1 且正因數多於兩個的整數,例如 12 或 91。
- 質因數分解
- 將一個數寫成質數的乘積,例如 \(60 = 2^{2} \cdot 3 \cdot 5\)。根據算術基本定理,除了因數的順序外,分解結果是唯一的。
- 完全平方數
- 某整數的平方所得的數(例如 36 = 6²)。在其質因數分解中,每個指數都是偶數,且因數個數為奇數。
- 單位(1)
- 數字 1 是每個整數的因數。它既不是質數也不是合數,這使質因數分解保持唯一。
- 互質
- 兩個整數唯一的公共正因數是 1,即最大公因數為 1(例如 8 和 15)。互質的數本身不一定是質數。
- 因數個數
- 若 \(N = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}\),則正因數個數等於所有質數的(指數 + 1)之積:\((a_{1}+1)(a_{2}+1)\cdots(a_{k}+1)\)。
常見問題
1 是質數還是合數?兩者都不是。依定義,質數恰好有兩個不同的因數;而 1 只有一個因數,因此它被歸類為「單位元」。
那 0 呢?任何整數都能整除 0,所以 0 在因數分解上是未定義的,會被視為既非質數也非合數。
為什麼完全平方數的因數個數是奇數?因為它的平方根會與自己配成一對(以 36 為例,這一對是 (6, 6)),所以這個因數只計算一次而非兩次。