最大公因數點計

最大公因數（Greatest Common Divisor, GCD）也稱為最大公約數，是指兩個或更多整數的共有最大因子。在數學中，通常使用質因數分解或者歐幾里得算法（Euclidean algorithm）來計算最大公因數。

歐幾里得算法是一種計算兩個整數最大公因數的算法，由古希臘數學家歐幾里得提出。這個算法的基本思想是，如果被除數能被除數整除，那麼被除數就是它自己和除數的最大公因數。如果不能整除，則繼續用除數去除餘數，直到餘數為0為止。此時，上一個非零餘數就是被除數和除數的最大公因數。

以下是一個使用歐幾里得算法計算最大公因數的例子：

假設我們需要計算56和28的最大公因數。

1. 首先，我們將兩個數中較大的數（56）除以較小的數（28），得到一個餘數。 56 ÷ 28 = 2，餘數為0。

2. 因為餘數為0，所以28是56和28的最大公因數。

然而，如果兩個數的差不是質數，我們需要繼續使用歐幾里得算法來找出它們的最大公因數。例如，如果我們需要計算12和18的最大公因數，我們可以這樣做：

1. 12 ÷ 18 = 0，餘數為12。
2. 18 ÷ 12 = 1，餘數為6。
3. 12 ÷ 6 = 2，餘數為0。

因此，6是12和18的最大公因數。

在實際應用中，歐幾里得算法可以很容易地用代碼實現，尤其是在計算機科學中。以下是一個簡單的Python代碼示例，用來計算兩個數的最大公因數：

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

# 使用示例
gcd_of_12_and_18 = gcd(12, 18)
print(gcd_of_12_and_18)  # 輸出: 6

這個算法的時間複雜度為O(log(max(a, b)))，其中a和b是被計算最大公因數的兩個數。