歐幾里得算法（輾轉(zhuǎn)相除法）

在一個除法算式中，被除數(shù)與除數(shù)的最大公因數(shù)等于除數(shù)與余數(shù)的最大公因數(shù)，這是輾轉(zhuǎn)相除法用于計算最大公因數(shù)的最根本的依據(jù)。
輾轉(zhuǎn)相除法就是反復應用上述規(guī)律（被除數(shù)與除數(shù)的最大公因數(shù)等于除數(shù)與余數(shù)的最大公因數(shù)）得到一系列的算式，后一個算式是將前一個算式的除數(shù)和余數(shù)分別作被除數(shù)和除數(shù)進行的除法，最后一個不等于0的余數(shù)就是所求的最大公因數(shù)。

給定a,b兩個數(shù)，假設a>b,那么（a,b)=(b,a-b)
再確定b,a-b大小,
用大數(shù)減小數(shù)，重復這個過程直到其中有一個數(shù)整除另一個數(shù)，這個數(shù)就是最大公約數(shù)

就是把上一輪有余數(shù)的除法計算中，
除數(shù)變?yōu)橄乱惠営嬎愕谋怀龜?shù)，
余數(shù)變?yōu)橄乱惠営嬎愕某龜?shù)，
一直這樣計算下去，
直到最后一次計算余數(shù)為零，
在最后一輪計算中的被除數(shù)，即為所求的最大公約數(shù)。
舉例：
105和85的最大公約數(shù)
第一輪計算
105÷85=1...20
第二輪計算
85÷20=4...5
第三輪計算
20÷5=4
第三輪沒有余數(shù)，
因此
105和85的最大公約數(shù)就是第三輪計算的被除數(shù)
5.
至于C語言編程，下邊是我自己寫的G函數(shù)(思想就是輾轉(zhuǎn)相除法求最大公約數(shù))
int
G(int
x,int
y)
{
int
t;
while(y!=0)
{
t=x%y
;
x=y;
y=t;
}
return
x;
}