最小公因數演算法

最小公因數（Greatest Common Divisor, GCD）是數論中的一個基本概念，它指的是兩個或更多整數的公有的最大因數。在數學中，通常使用歐幾里得算法（Euclidean algorithm）來計算兩個整數的最小公因數，這個算法也是最著名的演算法之一。

歐幾里得算法的基本思想是：兩個整數a和b的GCD可以通過a除以b的餘數來計算，並且這個餘數與a和b的GCD相同。具體來說，如果a除以b的餘數是r，那麼a和b的GCD等於b和r的GCD。

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

假設我們需要計算12和18的最小公因數。

1. 首先，我們將較大的數18除以較小的數12，得到餘數r。 18 ÷ 12 = 1, r = 6

2. 然後，我們將上一步得到的餘數6（現在是較大的數）除以12（現在是較小的數），得到新的餘數。 6 ÷ 12 = 0, r = 6

3. 因為餘數為0，這意味著6可以被12整除，所以12和6的GCD就是6。

4. 因此，12和18的GCD也是6。

這個算法可以很容易地擴展到任意數量的整數，只需要在每一步中選擇餘數和較小的數進行下一步計算。

在實際應用中，歐幾里得算法被廣泛用於各種數學領域，尤其是在數論、代數和計算機科學中。在計算機科學中，這個算法可以用來解決各種問題，例如在線性代數中用來解線性方程組，在圖論中用來檢測圖形的連通性，以及在加密系統中用來生成密鑰對等。