短除法（division method）進行質因數分解是一種系統化的技巧，透過反覆將大於 1 的整數除以最小的可能質數，直到商變成 1，藉此將該數拆解成其質因數。質數是指大於 1、且唯一因數只有 1 和本身的整數，例如 2、3、5、7、11、13、17、19、23 和 29；而合數則至少有一個除了 1 和本身之外的因數，因此可以被拆成一組質數的乘積。短除法是教授最廣泛的拆解方式，因為它只需要一支筆和一張紙、一份可用的質數清單，以及持續除下去的意願。它之所以一定可行，是依據算術基本定理（Fundamental Theorem of Arithmetic），該定理保證每個大於 1 的整數都恰好只有一組質因數分解（忽略因數的順序）。這個保證使得 360 無論由誰來除、以什麼順序除，都會得到 2 × 2 × 2 × 3 × 3 × 5。
短除法求質因數分解
短除法是試除法（trial division）的結構化版本：將你的數字寫在欄位的最上方，將它除以能整除的最小質數，把商寫在下方，然後對該商重複同樣的步驟，直到得到 1。因為每個合數都有一個最小的質因數——若數字為偶數則是 2，依此類推——所以這個過程一定會持續進行，直到最後得到 1。
由於它所產生的欄位排列方式，這個方法有時也被稱為梯形法（ladder method）或反覆除法（repeated division method）：
360 ÷ 2 = 180 180 ÷ 2 = 90 90 ÷ 2 = 45 45 ÷ 3 = 15 15 ÷ 3 = 5 5 ÷ 5 = 1左側作為除數的質數——2、2、2、3、3、5——正好就是原數的質因數，而它們出現的順序並不重要，重要的是這個多重集合（multiset）。橫向讀取最底下的結果即可得到質因數分解，將重複出現的質數以指數合併則可寫成精簡形式 2³ × 3² × 5。
如何使用短除法找出質因數分解
請依照以下具體步驟，使用短除法分解任何大於 1 的整數。範例數字為 84。
- 將該整數寫在欄位的最上方，在其下方畫一條水平線。在本示範中，範例數字為 84。
- 嘗試除以 2。如果該數為偶數，2 就是它的因數——在線的左側寫下 2，執行除法，並把商寫在下方。84 ÷ 2 = 42。
- 對新的商再嘗試除以 2。42 ÷ 2 = 21。21 是奇數，所以 2 不再是它的因數——改用下一個質數。
- 嘗試除以 3。21 ÷ 3 = 7。7 是質數，但還不要停下來——只要商仍然是合數，就繼續除下去。
- 嘗試下一個尚未用過且能整除的質數。7 ÷ 7 = 1。此時商已變成 1，方法結束。
- 依序收集所有用過的除數：2、2、3、7。將它們寫成乘積：2 × 2 × 3 × 7，再轉換為指數形式：2² × 3 × 7。
一個小型的安全規則：只要目前的商已經是質數，你就可以提早結束欄位——不需要一定除到 1。此時，剩下的那個質數就直接留作因數，仍然算數。例如分解 39 時，你會得到 13 ÷ 13 = 1 並停止；不過停在 13 也是可以的，因為 13 本身是質數，而且就是最後一個因數。
完整範例：逐步分解 360
360 是一個有用的範例，因為它有三個不同的質數，且其中一個質數出現了三次。以手動方式逐步執行短除法會得到下列序列。
| 步驟 | 被除數 | 最小質數 | 商 |
|---|---|---|---|
| 1 | 360 | 2 | 180 |
| 2 | 180 | 2 | 90 |
| 3 | 90 | 2 | 45 |
| 4 | 45 | 3 | 15 |
| 5 | 15 | 3 | 5 |
| 6 | 5 | 5 | 1 |
讀出這些除數會得到 2、2、2、3、3、5，因此 360 的質因數分解為 2 × 2 × 2 × 3 × 3 × 5，精簡寫法為 2³ × 3² × 5。指數代表重複出現的因數：2³ 表示三個 2 相乘，3² 表示兩個 3 相乘。若要驗算答案，把質因數再乘回去：2 × 2 = 4，4 × 2 = 8，8 × 3 = 24，24 × 3 = 72，72 × 5 = 360。乘積回到原來的數字，即可確認這個質因數分解正確。
為什麼短除法一定可行
兩個數學上的定理保證了短除法一定會在有限步驟內結束，並產生完整且唯一的質因數分解。
第一個是算術基本定理。它說明每個大於 1 的整數都可以寫成質數的乘積，而且這個分解在忽略因數順序的情況下是唯一的。因為質因數是唯一的，所以同一個數不會有兩種不同的質因數分解，而短除法必然會得到唯一正確的那一組。
第二個是一個實用的捷徑：只要目前處理的商比下一個要嘗試的最小質數的平方還小，就可以停止。更簡單地說，你只需要測試到原數的平方根為止的質數。以 360 為例，它的平方根大約是 18.97，所以一旦你除到 5——也就是小於 19 的質數——並將它除盡得到 1，就完成了。任何在自身平方根之內都無法被任何質數整除的剩餘數，本身必定是質數，這就是「剩餘即質數」捷徑安全無虞的原因。
數字 1 沒有質因數分解，因為 1 不是質數，而且沒有大於 1 的因數。每個大於 1 的整數都可以乾淨地分解。質數本身的分解是平凡的：7 的質因數分解就是 7，97 的質因數分解就是 97，而短除法會出現一步「質數除以自身等於 1」的除法步驟。
用計算機跳過冗長的除法
為了核對作業、課堂示範或快速的合理性檢查，相同的短除法可以自動化執行。質因數分解計算機會在你的瀏覽器中執行短除法，並在你輸入時即時更新結果。它接受任何大於 1、最多到 1,000,000,000,000（一兆）的整數，因此無論是課堂範例 84，或是 13 位數的挑戰題都能處理。
使用計算機的步驟和手算一樣，只要三個動作：
- 在大於 1 的整數欄位中輸入數字，例如 360。
- 即時查看質因數分解、指數形式（2³ × 3² × 5），以及因子樹的更新結果。
- 讀出質因數列表、因數個數，以及該數是否為質數。
因為這個工具在內部使用的就是試除法——盡可能地除以 2，接著除以 3、5、7，依此類推，直到剩下數字的平方根——所以它實際上就是上文所描述的短除法，只是替你執行而已。像 600,851,475,143 這樣的大數（等於 71 × 839 × 1471 × 6857），仍然可以在遠遠不到一秒的時間內分解完成。所有運算都在瀏覽器本地端執行，因此輸入的內容不會被上傳到任何伺服器。
讓質因數發揮實際作用
短除法的成果用途遠不止於將一個數寫成質數的乘積。指數形式 2^e₁ × 3^e₂ × … 可以直接支援接下來你可能想做的其他幾項計算。
| 用途 | 質因數如何幫助 | 快速方法 |
|---|---|---|
| 因數個數 | 將每個指數加 1，再相乘。 | (e₁ + 1)(e₂ + 1)… |
| 因數之和 | 將各質數次方的因數和相乘。 | ∏ (p^(e+1) − 1) / (p − 1) |
| 最大公因數（GCD） | 取每個質數指數的較小值。 | min(e₁, f₁), min(e₂, f₂)… |
| 最小公倍數（LCM） | 取每個質數指數的較大值。 | max(e₁, f₁), max(e₂, f₂)… |
| 化簡分數 | 約掉分子與分母中都出現的質因數。 | 將分子與分母同除以 GCD。 |
對於 360 = 2³ × 3² × 5，因數個數為 (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24，因數之和為 (1+2+4+8) × (1+3+9) × (1+5) = 15 × 13 × 6 = 1170，而這 24 個因數可以藉由組合每個指數的選擇一一列出。質因數分解計算機會在給出質因數的同時一併回傳這些數字，因此你可以直接取用，不需要再重算一次。一旦你得到兩個數字的質因數分解，GCF 計算機或LCM 計算機就能完成剩下的工作；若想深入了解這些運算背後的數學原理，如何使用質因數分解計算 GCF指南以更多範例說明相同的 min/max 指數概念。
短除法也是通往更大主題的概念性入口：它是整數乘法的逆運算，是模算術的基礎，也是現代加密（例如 RSA）安全性的基石，因為分解極大的數字非常困難，這讓私钥得以保持隱密。
先用幾個小數字以手算方式練習短除法，再以質因數分解計算機逐一驗算，以建立對這個技巧的信心。
若想更深入了解，請參閱如何找出 100 到 200 之間的質數。