C找最大公因數

要找兩個或多個數的最大公因數（Greatest Common Divisor, GCD），可以使用以下方法：

1. 輾轉相除法（Euclidean algorithm）： 這個算法通過不斷用較大的數除以較小的數，直到得到兩個數相等為止，此時這兩個數的公約數就是最大公因數。

   步驟：

   • 用較大的數除以較小的數，得到餘數。
   • 用上一步中較大的數（除數）替換較小的數（被除數），用餘數替換較大的數。
   • 重複步驟2，直到兩個數相等。
   • 此時，這兩個數就是最大公因數。

2. 質因數分解法： 將每個數的質因數分解出來，然後找出所有相同的質因數，將它們相乘得到最大公因數。

3. 更相減損法： 這個方法適用於兩個數的情況，通過不斷交替減去較小的數，直到兩個數相等為止，此時這兩個數的公約數就是最大公因數。

4. 使用公式： 對於兩個數a和b，它們的最大公因數可以表示為： GCD(a, b) = GCD(b, a mod b) 其中，a mod b表示a除以b的餘數。

5. 使用程式語言的庫函式： 許多程式語言都提供了計算最大公因數的函式，可以直接調用這些函式來得到結果。

例如，要找到兩個數12和18的最大公因數，可以使用輾轉相除法：

12 ÷ 18 = 0 余 12 18 ÷ 12 = 1 余 6 12 ÷ 6 = 2 余 0

所以，最大公因數是6。

或者使用質因數分解法：

12 = 2^2 3 18 = 2 3^2

最大公因數是2 * 3 = 6。