欧几里得算法

昨天上算法课听到了这个算法,突发兴趣来写一篇blog。

欧几里得算法的用处

欧几里得算法也称为辗转相除法,是求解最大公约数的一种方法。

若有两个数a和b,求a和b的最大公约数,按照我们之前所学的东西,可能只会枚举a与b的因子,效率很低…

但欧几里得为我们提供了一个十分便捷的方法。

一个强大的定理

gcd(a,b) = gcd(b, a%b)

下面给出证明

设a与b的公约数为 k ,a=bx+y;
则 k|a 且 k|b ,有 a%b=y
又有y=a-bx, 所以 k|y。
即 k|a%b

再假设b 与 a%b的公约数为kk,得 kk|a,所以(a,b)与(b,a%b)的公约数相同,所以其最大公约数也相同。

即gcd(a,b)==gcd(b,a%b);

代码实现

任何数与0的最大公约数都是他本身,且根据gcd(a,b)==gcd(b,a%b)可得知

当gcd中余数为0时,另一个数就是最大公约数。

所以代码如下

int gcd(int a,int b)
{
    int outcome;
    int temp;
    while(b!=0)
    {
        temp=a%b;
        a=b;
        b=temp;
    }
    outcome=a;
    return outcome;
}

溜溜球,去学概率论了…


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

<<<<<<< Updated upstream ======= >>>>>>> Stashed changes