Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1244445
  • 博文数量: 261
  • 博客积分: 4196
  • 博客等级: 上校
  • 技术积分: 3410
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-17 17:05
文章分类

全部博文(261)

文章存档

2018年(1)

2017年(22)

2016年(2)

2015年(8)

2014年(27)

2013年(40)

2012年(161)

分类: C/C++

2015-01-13 15:55:59

    欧几里德算法又称,用于计算两个a,b的。

    其计算原理依赖于下面的定理:
定理:gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
证明:a可以表示成a = kb + r,则r = a mod b
          假设d是a,b的一个,则有d|a,d|b,而r = a - kb,因此d|r
          因此d也是(b,a mod b)的
          因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

设计方法
是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:(a > b)
    ⒈ 若 r 是 a ÷ b 的余数,且r不为0, 则
            gcd(a,b) = gcd(b,r)
    ⒉ a 和其倍数之最大公因子为 a。
    另一种写法是:
    ⒈ 令r为a/b所得余数(0≤r
            若 r= 0,算法结束;b 即为答案。
    ⒉ 互换:置 a←b,b←r,并返回第一步。

C程序实现
unsigned int Gcd(unsigned int M,unsigned int N)
{
    unsigned int Rem;
    if(M < N)
    {
        M = M + N;
        N = M - N;
        M = M - N;
    }
    while(N > 0)
    {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}
阅读(1361) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~