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

欧几里德算法又称辗转相除法，用于求两个数的最大公约数。

其实我们需要知道的是一个公式：gcd(a,b) = gcd(b,a%b)

现在我们来举个例子模拟一下：求gcd(48,30)

步骤：

48 = 30 * 1 + 18

30 = 18 * 1 + 12

18 = 12 * 1 + 6

12 = 6 * 2 + 0

那么，gcd(48,30) = 6    

我们可以写两种形式的辗转相除：递归和非递归。

递归的模板：

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return 
        gcd(b,a%b);
}

可以优化如下：

int gcd(int a,int b)
{
     return b ? gcd(b,a%b) : a;
}

非递归的模板：

int Gcd(int a, int b)
{
    while(b != 0)
    {
    　　int r = b;
    　　b = a % b;
    　　a = r;
    }
    return a;
}

然后求两个数的最小公倍数就是a*b/gcd(a,b);

OK!