利用輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)的最大公因數(shù) 程序如下：
//利用輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)的最大公因數(shù)
int gcd(int a, int b)
{
int r;
while(b)
{
r = a%b;
a = b;
b = r;
}
return a;
}
相關(guān)理論如下：
「輾轉(zhuǎn)相除法」又叫做「歐幾里得算法」，是公元前 300 年左右的希臘數(shù)學(xué)家歐幾里得在他的著作《幾何原本》提出的。利用這個(gè)方法,可以較快地求出兩個(gè)自然數(shù)的最大公因數(shù)，即 HCF 或叫做 gcd。所謂最大公因數(shù)，是指幾個(gè)數(shù)的共有的因數(shù)之中最大的一個(gè)，例如 8 和 12 的最大公因數(shù)是 4，記作 gcd(8,12)=4。
在介紹這個(gè)方法之前,先說(shuō)明整除性的一些特點(diǎn),注以下文的所有數(shù)都是正整數(shù),以后不再重覆.
我們可以這樣給出整除以的定義:
對(duì)於兩個(gè)自然數(shù) a 和 b，若存在正整數(shù) q，使得 a=bq，則 b 能整除 a，記作 b | a，我們叫 b 是 a 的因數(shù)，而 a 是 b 的倍數(shù)。那麼如果 c | a，而且 c | b，則 c 是 a 和 b 的公因數(shù)。
由此,我們可以得出以下一些推論：
推論一：如果 a | b，若 k 是整數(shù)，則 a | kb。因?yàn)橛?a | b 可知 ha=b，所以 (hk)a=kb，即 a | kb.
推論二：如果 a | b 以及 a | c，則 a | (b±c)。因?yàn)橛?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。因?yàn)橛?a | b 以及 b | a，可知 ha=b，a=kb，因此 a=k(ha)，hk=1，由於 h 和 k 都是正整數(shù)，故 h=k=1，因此 a=b。
輾轉(zhuǎn)相除法是用來(lái)計(jì)算兩個(gè)數(shù)的最大公因數(shù)，在數(shù)值很大時(shí)尤其有用而且應(yīng)用在電腦程式上也十分簡(jiǎn)單。其理論如下：
如果 q 和 r 是 m 除以 n 的商及余數(shù)，即 m=nq+r，則 gcd(m,n)=gcd(n,r)。 證明是這樣的:
設(shè) 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。
因?yàn)?a | b 并且 b | a，所以 a=b，即 gcd(m,n)=gcd(n,r)。
舉例計(jì)算 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
此處再添加一個(gè)程序例子，不過(guò)不是利用輾轉(zhuǎn)相除法
求最大公約數(shù)和最小公倍數(shù):
#include <iostream>
using namespace std;
int gec,lcm;
void process(int x,int y)
{
gcd=x<y?x:y;
lcm=x<y?y:x;
for(gcd=x<y?x:y;gcd>1;gcd--)if(x%gcd==0&&y%gcd==0)break;
for(lcm=x<y?x:y;lcm>1;lcm++)if(lcm%x==0&&lcm%y==0)break;
return;
}