求最大公因數最快方法是什麼

最大公因數（Greatest Common Divisor），也稱最大公約數，是指兩個或多個整數共有約數中最大的一個。a、b 的最大公約數記為 (a, b)。那麼，如何快速求出最大公因數呢？以下介紹三種常用且高效的方法。

1. 短除法

短除法是求多個數最大公因數的常用方法。將所有數同時除以公有的質因數，直到兩兩互質為止，所有除數的乘積即為最大公因數。

示例：求 180 和 324 的最大公因數

180 和 324 同時除以 2、2、9（且 5 與 9 互質），因此最大公因數為 2 × 2 × 9 = 36。

2. 觀察法（利用整除特徵）

若兩數均能被小質數（如 2、3、5）整除，可先提取公因數，再進一步判斷。

示例：求 225 和 105 的最大公因數

225 和 105 均可被 3 和 5 整除，因此至少含有公因數 15。
225 ÷ 15 = 15，105 ÷ 15 = 7，且 15 與 7 互質，故最大公因數為 15。

3. 質因數分解法

將兩數分別分解質因數，取所有共有的質因數（相同質因數取最小次冪），相乘即得最大公因數。

示例：求 125 和 300 的最大公因數

125 = 5³，300 = 2² × 3 × 5²
共有質因數為 5²，因此最大公因數為 25。

以上三種方法分別適用於不同情境：短除法適合多數快速求解；觀察法適用於數字具有明顯整除特徵；質因數分解法適合理論分析或小數運算。實際使用時可靈活選擇最高效的方式。