昨天上算法课听到了这个算法，突发兴趣来写一篇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;
}

溜溜球，去学概率论了…