什麼是質因數分解?
質因數分解就是把一個整數拆解成相乘後能得到它的那一組質數。所謂質數,是指大於 1,且除了 1 與本身之外沒有其他因數的數(例如 2、3、5、7、11……)。根據「算術基本定理」,每一個大於 1 的整數都只有唯一一種質因數分解方式(因數的排列順序不計)。
如何使用這個計算機
輸入任何 2 以上的整數,再按下計算即可。本工具會以兩種格式呈現分解結果:一是展開式(把每個質因數逐一列出),二是較簡潔的指數式(將重複出現的質因數合併寫成次方)。此外,它還會告訴你出現了幾個相異質因數、含重數的質因數總個數,以及這個數本身是否為質數。
公式原理說明
本計算機採用試除法。它從最小的質數 2 開始,只要能整除,就反覆用每一個候選因數 \(d\) 去除這個數,並記錄各因數整除的次數。試除只需做到 \(\sqrt{n}\) 為止,因為若在平方根以下都找不到任何因數,剩下的數本身必定是質數。最終結果會表示成 $$n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$$
實例演算
以 \(n = 360\) 為例。先除以 2 三次:360 → 180 → 90 → 45(\(2^3\))。再除以 3 兩次:45 → 15 → 5(\(3^2\))。最後除以 5 一次:5 → 1(\(5^1\))。因此 $$360 = 2^3 \times 3^2 \times 5$$ 展開後就是 \(2 \times 2 \times 2 \times 3 \times 3 \times 5\):共有三個相異質因數、總計六個質因數。
質數與常見因數分解參考
質數是大於 1 的整數,且其正因數只有 1 與它自己。小於 100 的質數恰好有 25 個。數字 1 既不是質數也不是合數,而 2 是唯一的偶質數。
| 範圍 | 質數 | 個數 |
|---|---|---|
| 1–9 | 2, 3, 5, 7 | 4 |
| 10–19 | 11, 13, 17, 19 | 4 |
| 20–29 | 23, 29 | 2 |
| 30–39 | 31, 37 | 2 |
| 40–49 | 41, 43, 47 | 3 |
| 50–59 | 53, 59 | 2 |
| 60–69 | 61, 67 | 2 |
| 70–79 | 71, 73, 79 | 3 |
| 80–89 | 83, 89 | 2 |
| 90–99 | 97 | 1 |
常見數字的質因數分解(指數形式):
| 數字 | 質因數分解 | 因數個數 |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 24 | 2³ × 3 | 8 |
| 36 | 2² × 3² | 9 |
| 48 | 2⁴ × 3 | 10 |
| 60 | 2² × 3 × 5 | 12 |
| 100 | 2² × 5² | 9 |
| 120 | 2³ × 3 × 5 | 16 |
| 144 | 2⁴ × 3² | 15 |
| 210 | 2 × 3 × 5 × 7 | 16 |
| 360 | 2³ × 3² × 5 | 24 |
| 1000 | 2³ × 5³ | 16 |
| 1024 | 2¹⁰ | 11 |
解讀你的結果
指數形式 \(n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}\) 列出每個相異質數 \(p_i\),以及它整除 \(n\) 的次數。
- 因數個數:等於 \((a_1+1)(a_2+1)\cdots(a_k+1)\)。以 \(360 = 2^3 \times 3^2 \times 5\) 為例,即 \((3+1)(2+1)(1+1) = 24\) 個因數。
- 質數判定:只有一個指數為 1 的質數,表示該數是質數,其唯一因數為 1 與它自己。
- 完全平方數:若所有指數皆為偶數,則該數為完全平方數。以 \(144 = 2^4 \times 3^2\) 為例,指數減半得 \(2^2 \times 3 = 12\),因此 \(\sqrt{144} = 12\)。
- 最大公因數與最小公倍數:求最大公因數時,取每個共同質數的較小指數;求最小公倍數時,取每個質數的較大指數。以 \(360 = 2^3 \times 3^2 \times 5\) 與 \(84 = 2^2 \times 3 \times 7\) 為例:最大公因數 = \(2^2 \times 3 = 12\),最小公倍數 = \(2^3 \times 3^2 \times 5 \times 7 = 2520\)。驗算:\(12 \times 2520 = 30240 = 360 \times 84\)。
- 化簡分數:將分子與分母同除以它們的最大公因數。\(\frac{84}{360} = \frac{84 \div 12}{360 \div 12} = \frac{7}{30}\)。
大數。將兩個大質數相乘很容易,但要從乘積(半質數)還原出這兩個質數,據信對傳統電腦而言非常困難。試除法在數字達到數百位之前就已變得不切實際。RSA 加密正是利用這種不對稱性,使用 2048 位元或更長的模數。請注意,1 沒有質因數,而 0 沒有質因數分解。
常見問題
為什麼數字至少要是 2?因為 0 和 1 沒有質因數分解——1 既不是質數,也不是合數。
「含重數」是什麼意思?就是每個質因數出現幾次就計算幾次。以 360 為例,總數是 6(三個 2、兩個 3、一個 5)。
1 是質數嗎?不是。依定義,質數必須恰好有兩個相異的正因數,而 1 只有一個因數。