c中求最大公因子算法及解析

int gcd(int m, int n)
{
    int r;
    while(n!=0)
    {
        r=(m>=n)?(m-n):m;
        m=n;
        n=r;
    }
    return m;
}


「辗转相除法」又叫做「欧几里得算法」,是公元前 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


评论: 5 | 引用: 0 | 查看次数: 10751
回复回复晕晕[2007-07-07 09:26 PM | del]
什么烂网.
回复回复咪咪[2007-06-01 09:02 AM | del]
猫猫儿童节快乐!

今天要吃儿童餐!哈.......
回复回复咪咪[2007-05-30 11:38 AM | del]
竟然拿我的人格起誓,来人哪,拖出去脱光光挂在阳台上晾着.!
回复回复dashu126[2007-05-30 09:59 AM | del]
也许,或者,可能。。。我的主观判断是有误。。

可是她的东西第一眼看过去。。真的很难做出其它的判断。。

中国的美食讲究的是:色、香、味,俱全。。

也许summer应该学一下摄影技术,,,

从不同的角度,光线的强弱,等方面取图,,

然后再给图片做上各种效果。。(人靠衣裳马靠鞍)

。。。。。。

最后,我以咪咪的人格发誓,,,我绝无伤害他人之心。。

也许是我在措词方面不行,原谅我是学计算机的,不是学文学的。。

想到什么说什么。。不会考虑多个同义词之间如何使用。
回复回复咪咪[2007-05-30 09:16 AM | del]
猫儿哦,关于那个summer的事,我看他你在她博里的那个评论啦,说得可有点不客气的啦....

嗯,她是我后来认识的一个博友,人很好的哦,在认识她之前我就开始做各种菜菜(悖逆称之为怪怪的东西)啦,所以哦,不是被她带坏啊什么的;

你那样说人家做的蛋糕,她很伤心呢....你说怎么办呢?
发表评论
昵 称:
密 码: 游客发言不需要密码.
内 容:
验证码: 验证码
选 项:
虽然发表评论不用注册,但是为了保护您的发言权,建议您注册帐号.
字数限制 1000 字 | UBB代码 开启 | [img]标签 开启