最大公因數計算機 - 數字最大公因數

最大公因數（GCF），也稱為最大公約數（GCD）或最高公因數（HCF），是能整除一組指定整數中每個數且沒有餘數的最大正整數。例如，12 和 18 的最大公因數是 6，因為 6 是能同時整除 12 和 18 的最大數。 計算最大公因數最常見的兩種演算法是歐幾里得演算法與質因數分解。對大數而言，歐幾里得演算法更有效率。它會反覆把一對數字 (a, b) 替換成 (b, a mod b)，直到餘數為 0；最後一個非零的 b 就是最大公因數。這個演算法只需 O(log min(a,b)) 步，即使是非常大的整數也能快速完成。 質因數分解則是把每個數表示成質數次方的乘積，再取各質數在所有數中出現的最小次方並相乘。例如，12 = 2^2 * 3，18 = 2 * 3^2，因此 GCF(12, 18) = 2^1 * 3^1 = 6。雖然對大數來說不如歐幾里得演算法有效率，但質因數分解能清楚說明為什麼最大公因數會是這個值。 最大公因數有許多實際用途。在算術中，它可用來把分數約成最簡形式：要化簡 a/b，只要把分子和分母同除以 GCF(a, b)。在幾何中，兩個長度的最大公因數代表可以同時測量兩者且沒有餘數的最長刻度單位。在電腦科學中，最大公因數會出現在模運算、密碼學演算法（如 RSA 金鑰產生）以及資料壓縮中。 對於兩個以上的數字，最大公因數會以迭代方式計算。GCF(a, b, c) = GCF(GCF(a, b), c)。這個計算機可處理任意數量的正整數，並支援歐幾里得演算法（快速得到結果）與質因數分解（顯示詳細步驟）。質因數分解檢視特別適合正在學習因數與整除性的學生。