基本介紹
- 中文名:輾除法
- 別名:歐幾里德算法
證明,另一種寫法,使用循環,相關代碼,最大公約數,整除性定義,
證明
設兩數為a、b(b<a),求它們最大公約數(a、b)的步驟如下:用a/b,得a/b=q......r1(0≤r)。若r1=0,則(a,b)=b;若r1≠0,則再用b/r1,得b/r1=q......r2 (0≤r2).若r2=0,則(a,b)=r1,若r2≠0,則繼續用r1/r2,……如此下去,直到能整除為止。其最後一個非零餘數即為(a,b)。
[編輯] 算法
1. 若 r 是 a ÷ b 的餘數, 則
gcd(a,b) = gcd(b,r)
2. a 和其倍數之最大公因子為 a。
另一種寫法
1. a ÷ b,令r為所得餘數(0≤r<b)
若 r = 0,算法結束;b 即為答案。
2. 互換:置 a←b,b←r,並返回第一步。
[編輯] 虛擬碼
這個算法可以用遞歸寫成如下:
function gcd(a, b) {
if b<>0
return gcd(b, a mod b);
else
return a;
}
使用循環
function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}
pascal代碼(遞歸)
相關代碼
具體標準C語言代碼
void main() { int a,b,num1,num2,temp; printf("please input two numbers:\n"); scanf("%d,%d",&num1,&num2); if(num1<num2)//這裡if語句在C編譯環境下可以去除 { temp=num1; num1=num2; num2=temp; } a=num1; b=num2; while(b!=0)/*利用輾除法,直到b為0為止*/ { temp=a%b; a=b; b=temp; } printf("Common factor:%d\n",a); printf("Common multiple:%d\n",num1*num2/a); }
最大公約數
求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
其中“a mod b”是指取 a ÷ b 的餘數。
例如,123456 和 7890 的最大公因子是 6, 這可由下列步驟看出:
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0
輾轉相除法的運算速度為 O(n2),其中 n 為輸入數值的位數。
輾轉相除法原理及其詳細證明如下:
最大公約數(greatest common divisor,簡寫為gcd;或highest common factor,簡寫為hcf)
所謂最大公因數,是指幾個數的共有的因數之中最大的一個,例如 8 和 12 的最大公因數是 4,記作gcd(8,12)=4。
整除性定義
在介紹這個方法之前,先說明整除性的一些特點(下文的所有數都是正整數,不再重覆),我們可以這樣給出整除性的定義:
對於二個自然數a和b,若存在正整數q,使a=bq,則a能被b整除,b為a的因子,a為b的倍數。
由此我們可以得出以下推論:
推論1、如果a能被b整除(a=qb),若k為正整數,則ka也能被b整除(ka=kqb)
推論2、如果a能被c整除(a=hc),b也能被c整除(b=tc),則(a±b)也能被c整除
因為:將二式相加:a+b=hc+tc=(h+t)c 同理二式相減:a-b=hc-tc=(h-t)c
所以:(a±b)也能被c整除
推論3、如果a能被b整除(a=qb),b也能被a整除(b=ta),則a=b
因為:a=qb b=ta a=qta qt=1 因為q、t均為正整數,所以t=q=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=gcd(m,n)