Java辗除法求两个自然数的最大公因数

利用辗转相除法求两个自然数的最大公因数 程序如下：
[size=xx-large]

//利用辗转相除法求两个自然数的最大公因数
int gcd(int a, int b)
{
    int r;
    while(b)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}
相关理论如下：
    「辗转相除法」又叫做「欧几里得算法」，是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的。利用这个方法,可以较快地求出两个自然数的最大公因数，即 HCF 或叫做 gcd。所谓最大公因数，是指几个数的共有的因数之中最大的一个，例如 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



此处再添加一个程序例子，不过不是利用辗转相除法
求最大公约数和最小公倍数:
          #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;
         }

[/size]