求解两个数的最大公约数和最小公倍数

已知m，n(m > 0，n > 0)的最大公约数为p，那么m，n的最小公倍数q = m * n / p。所以只需要求得p即可得到q。求最大公约数有如下两种方法。

方法一：
int gcd1(int m, int n)
{
    int min;
    min = (m < n) ? m : n;
    for(; (m % min) || (n % min);)
        min--;
    return min;
}

方法二：
int gcd2(int m, int n)
{
    while(n)
    {
        int temp = n;
        n = m % n;
        m = temp;
    }
    return m;
}

方法二称为欧几里得算法，又称为辗转相除法，其思路如下：
假设m1 = n1 * d1 + r1，若r1 == 0，则n1为m1和n1的最大公约数；若r1 != 0，则n1和r1的最大公约数就是m1和n1的最大公约数。令m2 = n1，n2 = r1，有 m2 = n2 * d2 + r2，若r2 == 0，则n2为m2和n2的最大公约数，也就是n1和r1的最大公约数；若r2 != 0，则n2和r2的最大公约数就是m2和n2的最大公约数，也就是n1和r1的最大公约数......反复下去，直到余数为0。下面是辗转相除法的一个实例。
17085 = 7035 * 2 + 3015;
7035 = 3015 * 2 + 1005;
3015  = 1005 * 3 + 0;
只需要循环三次就可计算出17085和7035的最大公约数为1005，如果按照方法一，则需要循环7035 - 1005 = 6030次。
上面分析的是m大于n的情形，如果m小于n呢？
7035 = 17085 * 0 + 7035;
17085 = 7035 * 2 + 3015;
7035 = 3015 * 2 + 1005;
3015  = 1005 * 3 + 0;
相比m大于n的情形，只是多了一次循环而已。
方法二的递归实现如下：
int gcd3(int m, int n)
{
    return n ? gcd3(n, m % n) : m;
}