最大公因數演算法

最大公因數（Greatest Common Divisor, GCD）的演算法有很多種，其中最著名的是歐幾里得算法（Euclidean algorithm），又稱為輾轉相除法。這個算法可以用來計算兩個整數的最大公因數，其基本思想是：兩個數的最大公因數等於其中較小的數和兩個數相除的餘數的最大公因數。

以下是歐幾里得算法的偽代碼：

function gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

這個算法的時間複雜度為O(log(max(a, b)))，因為最多需要執行log(max(a, b))次除法操作。

除了歐幾里得算法之外，還有其他一些計算最大公因數的算法，例如：

1. 質因數分解法：將兩個數分別分解質因數，然後找出共同的質因數，求和即得最大公因數。
2. 快速傅立葉變換（FFT）算法：對於某些特殊類型的整數（如素數的冪次），可以使用FFT算法來加速計算最大公因數。
3. 擴展歐幾里得算法：不僅可以求出最大公因數，還可以找出a和b的一個解，使得a x + b y = gcd(a, b)。

在實際套用中，通常使用歐幾里得算法來計算最大公因數，因為它的實現簡單，時間複雜度低，而且對於大多數情況下的整數都足夠高效。