最大公約數
如果有一個自然數 能被自然數 整除,則稱 為 a的倍數, b 為 a 的約數。幾個自然數公有的約數,叫做這幾個自然數的公約數。公約數中最大的一個公約數,稱為這幾個自然數的最大公約數。
輸入 a和 b, 請傳回 a和 b的最大公約數。
歐幾裡德算法
歐幾裡得算法又稱輾轉相除法,是指用于計算兩個非負整數a,b的最大公約數。應用領域有數學和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。
假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾裡得算法,是這樣進行的:
a b c
1997 / 615 = 3 (餘 152)
615 / 152 = 4(餘7)
152 / 7 = 21(餘5)
7 / 5 = 1 (餘2)
5 / 2 = 2 (餘1)
2 / 1 = 2 (餘0)
至此,最大公約數為1
以除數和餘數反複做除法運算,當餘數為 0 時,取目前算式除數為最大公約數,是以就得出了 1997 和 615 的最大公約數 1。
代碼及詳情如下:
int gcd (int a, int b){
int c=0; //用來作餘數
while(b!=0){
c=a%b;
a=b;
b=c;
}
return a; //退出循環時b等于0,a等于上一個b的值,是以傳回a
}