首先看 代碼如下，代碼并不難，很多人都會寫。

public static int f(int a, int b){while(b != 0){int temp = b;b = a % b;a = temp;}return a;}

舉個例子，例如6，8按照代碼運行一遍。

a b 6 8 8 6 6 2 2 0

但是這個算法的原理可是折磨了我很久，不知道大家懂不懂這個原理

首先 摘自百度百科

兩個數的最大公約數是指能同時整除它們的最大正整數。 設兩數為a、b(a≥b)，求a和b最大公約數 的步驟如下：
(1)用a除以b(a≥b)，得 a / b = q…r1 。 (2)若 r1 = 0 ，則 (a, b) = b； (3)若 r1
不等于 0 ，則再用b除以 r1 ，得b / r1 = q…r2(此處q不是上方的q). (4)若 r2=0 ，則(a,b)=r1
；若 r2不等于0 ，則繼續用r1除以 r2 ，……，如此下去，直到能整除為止。 其最后一個余數為0的除數即為 (a,b)
的最大公約數。

為什么這樣進行遞歸除下去我也不懂，知道看到數論吧的以為大神發帖

假設有兩個數x和y，存在一個最大公約數z=(x,y)，即x和y都有公因數z，
那么x一定能被z整除，y也一定能被z整除，所以x和y的線性組合mx±ny也一定能被z整除。（m和n可取任意整數）

對于輾轉相除法來說，思路就是：若x>y，設x/y=n余c，則x能表示成x=ny+c的形式，將ny移到左邊就是x-ny=c，由于一般形式的mx±ny能被z整除，所以等號左邊的x-ny（作為mx±ny的一個特例）就能被z整除，即x除y的余數c也能被z整除。

由以上的推理可知 a / b的余數 也能被 (a,b)的最大公約數整除，因此就將問題轉化為求 其中較小的數和余數的最大公約數，最終將范圍不斷減小，從而求出答案。

總結

以上是生活随笔為你收集整理的辗转相除求最大公约数原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。