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

就是把上一輪有余數(shù)的除法計(jì)算中，
除數(shù)變?yōu)橄乱惠営?jì)算的被除數(shù)，
余數(shù)變?yōu)橄乱惠営?jì)算的除數(shù)，
一直這樣計(jì)算下去，
直到最后一次計(jì)算余數(shù)為零，
在最后一輪計(jì)算中的被除數(shù)，即為所求的最大公約數(shù)。
舉例：
105和85的最大公約數(shù)
第一輪計(jì)算
105÷85=1...20
第二輪計(jì)算
85÷20=4...5
第三輪計(jì)算
20÷5=4
第三輪沒有余數(shù)，
因此
105和85的最大公約數(shù)就是第三輪計(jì)算的被除數(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;
}

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