輾轉相除法
「輾轉相除法」又叫做「歐幾里得算法」,是公元前 300 年左右的希臘數學家歐幾里得在他的著作《幾何原本》提出的.利用這個方法,可以較快地求出兩個自然數的最大公因數,即 HCF 或叫做 gcd.
最大公約數（greatest common divisor，簡寫為gcd；或highest common factor，簡寫為hcf)
所謂最大公因數,是指幾個數的共有的因數之中最大的一個,例如 8 和 12 的最大公因數是 4,記作 gcd(8,12)=4.
在介紹這個方法之前,先說明整除性的一些特點,注以下文的所有數都是正整數,以后不再重覆.
我們可以這樣給出整除以的定義:
對於兩個自然數 a 和 b,若存在正整數 q,使得 a=bq,則 b 能整除 a,記作 b | a,我們叫 b 是 a 的因數,而 a 是 b 的倍數.
那麼如果 c | a,而且 c | b,則 c 是 a 和 b 的公因數.
由此,我們可以得出以下一些推論:
推論一:如果 a | b,若 k 是整數,則 a | kb.因為由 a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb.
推論二:如果 a | b 以及 a | c,則 a | (b±c).因為由 a | b 以及 a | c,可知 ha=b,ka=c,二式相加,得 (h+k)a=b+c,即 a | (b+c).同樣把二式相減可得 a | (b-c).
推論三:如果 a | b 以及 b | a,則 a=b.因為由 a | b 以及 b | a,可知 ha=b,a=kb,因此 a=k(ha),hk=1,由於 h 和 k 都是正整數,故 h=k=1,因此 a=b.
輾轉相除法是用來計算兩個數的最大公因數,在數值很大時尤其有用而且應用在電腦程式上也十分簡單.其理論如下:
如果 q 和 r 是 m 除以 n 的商及余數,即 m=nq+r,則 gcd(m,n)=gcd(n,r).
證明是這樣的:
設 a=gcd(m,n),b=gcd(n,r)
則有 a | m 及 a | n,因此 a | (m-nq)(這是由推論一及推論二得出的),即 a | r 及 a | n,所以 a | b
又 b | r 及 b | n,所以 b | (nq+r),即 b | m 及 b | n,所以b | a.因為 a | b 并且 b | a,所以 a=b,即 gcd(m,n)=gcd(n,r).
例如計算 gcd(546, 429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此
gcd(546, 429)
=gcd(429, 117)
=gcd(117, 78)
=gcd(78, 39)
=39
Java實現代碼如下:
package com;
public class GcdTest
{
//循環實現
int gcd1(int a, int b)
{
int k = 0;
do
{
//得到余數
k = a % b;
//根據輾轉相除法,把被除數賦給除數
a = b;
//余數賦給被除數
b = k;
} while (k != 0);
//返回被除數
return a;
}
//逆歸實現
int gcd2(int a,int b)
{
//直到滿足此條件逆歸退出
if(b == 0)
{
return a;
}
if(a < 0)
{
return gcd2(-a,b);
}
if(b < 0)
{
return gcd2(a,-b);
}
return gcd2(b,a % b);
}
public static void main(String[] args)
{
GcdTest gt = new GcdTest();
System.out.println(gt.gcd1(888,458));
System.out.println(gt.gcd2(888, 458));
}
}