最大公因數計算

最大公因數（Greatest Common Divisor, GCD），也稱為最大公約數，是指兩個或更多個數字中最大的那個共同因子。要計算兩個數字的最大公因數，可以使用以下方法：

1. 質因數分解法：將兩個數字分別分解為質因數的乘積，然後找出共同的質因數，將它們相乘得到最大公因數。

2. 長除法：用較大的數除以較小的數，得到一個餘數。然後用除數除以餘數，再次得到一個餘數。重複這個過程，直到餘數為0，此時的除數就是最大公因數。

3. 歐幾里得算法（Euclidean algorithm）：這是計算最大公因數的一種高效算法，其基本思想是：兩個數字的最大公因數等於它們中的較小數與兩數相除的餘數的最大公因數。

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

假設我們要計算數字24和36的最大公因數。

1. 初始化兩個數字：a = 24, b = 36。
2. 計算a除以b的餘數：r1 = a % b = 24 % 36 = 24。
3. 因為餘數不是0，所以我們需要更新a和b的值，讓a = b, b = r1。即a = 36, b = 24。
4. 再次計算餘數：r2 = a % b = 36 % 24 = 12。
5. 因為餘數不是0，所以我們再次更新a和b的值，讓a = b, b = r2。即a = 24, b = 12。
6. 再次計算餘數：r3 = a % b = 24 % 12 = 12。
7. 因為餘數不是0，所以我們再次更新a和b的值，讓a = b, b = r3。即a = 12, b = 12。
8. 這次餘數為0，所以最大公因數就是b的值，即最大公因數為12。

所以，數字24和36的最大公因數是12。