⚡ Gcf 計算機

最大公因數（GCF，英文也稱 greatest common divisor，GCD，即最大公約數）指的是能夠整除一組數字中每一個數的最大正整數。只要你輸入一串整數，這款計算機就會立刻找出它們共同的最大因數。無論是約分分數、化簡比例、因式分解，還是把數量平均分組，它都能派上用場。

畫面上只有一個輸入欄位，標示為 numbers（數字）。請輸入兩個或以上的整數，並以逗號分隔，例如 24, 36, 60。接著計算機會：

• 依逗號將你輸入的內容切開，並自動去除多餘的空白。
• 只保留有效的整數——它會比對 -?\d+ 這個格式，因此負數可以接受，但小數、分數與其他無關文字都會被忽略。
• 計算所有有效數字的最大公因數，並顯示結果。

由於非整數的內容會直接被過濾掉，輸入一串整齊、以逗號分隔的整數，就能得到最可靠的答案。

這款計算機並不會逐一測試每個可能的因數，而是運用「輾轉相除法」（歐幾里得演算法），每次處理兩個數字，再一路「合併」整串數列。簡單來說，它的運算過程是：

• 先用經典的 gcd 演算法求出 \gcd(a, b)。
• 接著計算 \gcd(該結果, c)，再算 \gcd(該結果, d)，依此類推處理整串數字。

之所以可行，是因為多個數字的最大公因數，等同於「目前累積結果」與「下一個數字」的最大公因數——這是一種高效且歷經驗證的方法。

假設你輸入 24, 36, 60：

• \gcd(24, 36) = 12
• \gcd(12, 60) = 12

因此計算機會回傳 12。你可以自行驗證：24 ÷ 12 = 2、36 ÷ 12 = 3、60 ÷ 12 = 5，全都是整數，而且沒有比 12 更大的數能同時整除這三個數字。

一組整數的最大公因數（GCF）是能夠整除每一個整數且無餘數的最大正整數。三種手動方法給出相同的答案；選擇適合你的數字大小的方法。

方法 1 — 質因數分解

1. 將每個數字寫成質數的乘積。例如：24 = 2^3 · 3 和 36 = 2^2 · 3^2。
2. 只保留出現在每個因數分解中的質數。這裡兩者都包含 2 和 3。
3. 給每個共同質數在各數字中的最小指數：2^{\min(3,2)} = 2^2 和 3^{\min(1,2)} = 3^1。
4. 將這些冪相乘：
   \gcd(24,36) = 2^2 · 3 = 4 · 3 = 12
   所以最大公因數是 12。
5. 如果沒有質數被所有數字共同擁有，最大公因數是 1。

方法 2 — 歐幾里得演算法（最適合大數字）

歐幾里得演算法完全避免因數分解。它基於以下事實：\gcd(a,b) = \gcd(b, a \bmod b)。

1. 將較大的數字除以較小的數字並保留餘數。
2. 將較大的數字替換為較小的數字，並將較小的數字替換為餘數。
3. 重複直到餘數為 0。最後的非零餘數是最大公因數。

對於 \gcd(1071, 462)：

1. 1071 = 2 × 462 + 147
2. 462 = 3 × 147 + 21
3. 147 = 7 × 21 + 0
4. 達到餘數 0，所以最後的非零餘數 21 是最大公因數。

方法 3 — 列舉因子（僅適用於小數字）

寫出每個數字的所有因子，圈出它們共同的因子，並取最大的。18 的因子：1, 2, 3, 6, 9, 18。30 的因子：1, 2, 3, 5, 6, 10, 15, 30。共同因子：1, 2, 3, 6 → 最大公因數 = 6。這種方法可靠但在數字超過兩位數時速度緩慢。

三個或更多數字 — 折疊規則

最大公因數具有結合性，所以你可以一次減少兩個數字的長列表：

例如，\gcd(30, 42, 70)：首先 \gcd(30,42) = 6，然後 \gcd(6,70) = 2。折疊的順序不會改變結果。因為每次折疊只能縮小執行中的值，所以一旦執行中的最大公因數達到 1 就可以提前停止。

符號無關緊要：整除性忽略符號，所以 \gcd(-a,b) = \gcd(a,b)，最大公因數始終報告為正數。

三個值得記住的恆等式

對於任何兩個非零整數 a 和 b，最大公因數和最小公倍數的乘積等於乘積的絕對值：

所以一旦你知道最大公因數，你就能免費得到最小公倍數：用 a = 24、b = 36 和 \gcd = 12，我們得到 lcm = (24 × 36) / 12 = 864 / 12 = 72。小心：這個恆等式僅適用於兩個數字 — 它不能不改變地擴展到三個或更多。

第二個恆等式處理零：每個整數都整除 0，所以

這就是為什麼在列表中添加 0 永遠不會改變答案，以及為什麼 \gcd(0,0) 按慣例定義為 0。

例 1 — 互質對：gcd(14, 25)

質因數分解：14 = 2 · 7 和 25 = 5^2。這兩個列表根本不共享任何質數，所以唯一的公因子是 1。

用歐幾里得演算法檢查：

1. 25 = 1 × 14 + 11
2. 14 = 1 × 11 + 3
3. 11 = 3 × 3 + 2
4. 3 = 1 × 2 + 1
5. 2 = 2 × 1 + 0

最後的非零餘數是 1，所以 \gcd(14,25) = 1，這兩個數字互質。因此，像 \tfrac{14}{25} 這樣的分數已經是最簡形式。

例 2 — 簡化分數 84/126

1. 因數分解兩部分：84 = 2^2 · 3 · 7，126 = 2 · 3^2 · 7。
2. 共同質數在其最低指數處：2^1 · 3^1 · 7^1。
3. 相乘：2 · 3 · 7 = 42，所以最大公因數是 42。
4. 將分子和分母除以 42：
   ((84) ÷ (126)) = ((84 ÷ 42) ÷ (126 ÷ 42)) = ((2) ÷ (3))

因為 \gcd(2,3) = 1，結果是完全化簡的。除以小於最大公因數的任何值 — 比如 6，得到 \tfrac{14}{21} — 仍然還有工作要做。

例 3 — 含有負數的混合集合：gcd(−18, 45, 9)

首先去掉符號，因為整除性不依賴符號：任務變成 \gcd(18, 45, 9)。現在從左到右折疊。

1. \gcd(18,45)：45 = 2 × 18 + 9，然後 18 = 2 × 9 + 0 → 最大公因數是 9。
2. 折疊第三個數字：\gcd(9, 9) = 9。

所以 \gcd(-18, 45, 9) = 9。即使一個輸入是負數，答案也是正的，在這裡最大公因數等於其中一個輸入 — 當一個數字整除所有其他數字時，這總是會發生。

例 4 — 四個數字：gcd(48, 72, 120, 180)

通過質因數分解。因數分解每個：

質數 5 在 48 和 72 中缺失，所以被排除。共同質數在其最低指數處給出

通過歐幾里得折疊。使用 \gcd(a,b,c,d) = \gcd(\gcd(\gcd(a,b),c),d)：

1. \gcd(48,72)：72 = 1 × 48 + 24；48 = 2 × 24 + 0 → 24。
2. \gcd(24,120)：120 = 5 × 24 + 0 → 24。
3. \gcd(24,180)：180 = 7 × 24 + 12；24 = 2 × 12 + 0 → 12。

兩條路線一致：最大公因數是 12。通過除法檢查答案：48/12 = 4，72/12 = 6，120/12 = 10，180/12 = 15 — 都是整數，且 \gcd(4,6,10,15) = 1，確認沒有遺漏更大的值。