輾轉相除法最快

輾轉相除法（又稱為歐幾里得算法，Euclidean algorithm）是計算兩個整數最大公約數（Greatest Common Divisor, GCD）的有效方法。它的基本思想是：兩個整數的最大公約數等於它們中較小的數與兩數相除的餘數的最大公約數。

輾轉相除法的步驟如下：

1. 設兩個正整數為 ( a ) 和 ( b )，其中 ( a > b )。
2. 用 ( a ) 除以 ( b )，得到商 ( q ) 和餘數 ( r )，即 ( a = bq + r )，其中 ( 0 \leq r < b )。
3. 如果 ( r = 0 )，則 ( b ) 是 ( a ) 和 ( b ) 的最大公約數，算法結束。
4. 否則，將 ( a ) 和 ( b ) 的角色互換，用 ( b ) 除以 ( r )，繼續執行步驟 2 和 3，直到餘數為 0。

輾轉相除法是計算兩個整數最大公約數的一種非常高效的方法，它的時間複雜度為 ( O(\log \max(a, b)) )，其中 ( \max(a, b) ) 是 ( a ) 和 ( b ) 中的較大者。這是因為每次除法都會使被除數和除數減少，直到餘數為 0，這通常只需要幾次除法就可以實現。

輾轉相除法不僅可以用來計算兩個數的最大公約數，還可以用來解決其他相關的問題，例如解線性同餘方程、檢驗數字是否為質數等。