欧几里得算法证明与实现

算法简述

欧几里德算法又称辗转相除法，用于计算两个正整数 a，b 的最大公约数。定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数gcd(greatest common divisor)

求最大公约数常规的方法就是从 M，N(M>N)反向 N 循环与 M，N 进行取模运算，得到最大数，下面的方法时间复杂度为 O(logN)会更高效。

也可以看看hsfzxjy同学的证明过程https://segmentfault.com/q/1010000004427096

C 实现

#include<stdio.h>
unsigned int gcd(unsigned int M, unsigned int N)
{
    unsigned int rem;
    if(M < N)/*exchange value to=>M>N*/
    {
        int temp = M;
        M = N;
        N = temp;
    }

    while(N > 0)
    {
        rem = M % N;
        M = N;
        N = rem;
    }
    return M;
}
int main()
{
    printf("%d\n", gcd(25, 0));
    return 0;
}