欧几里德算法（最大公约数算法）

欧几里德算法的核心是辗转相除法：gcd(a,b)=gcd(b,a mod b)

证明：

1. 设c为a和b的最大公约数，数学表示gcd=(a,b)；因为任意两整数间必存在最大公约数，也就是说存在k1，k2，有a = k1*c, b=k2*c 。

2. a mod b ，余数r和k3有等价于

   r = a - b*k3

   = (k1 - k2*k3)c

   显然，a和b的余数为最大公约数的倍数

当 余数r为 0时，则输出gcd的左值（b）

C语言：

//功能：利用欧几里德算法，求整数a，b的最大公约数
//参数：整数a，b
//返回：a,b的最大公约数
1.
int gcd(int a,int b){
    while(a%b){//如果余数不为0，就一直进行辗转相除
        int r = a % b;//r为a和b的余数，即r = a mod(b);
        a = b;
        b = r;
    }
    return b;
}

更简洁的形式：

2.
int gcd(int a,int b)///位运算
{  
    while(b^=a^=b^=a%=b);  
    return a;  
}  


3.
int gcd(int a,int b)///递归调用
{
    if(b==0)
    {
        return a;
    }
    gcd(b,a%b);
}

4.
#include<algorithm>///直接使用c++的内置函数
using namespace std;
__gcd(int a,int b)