求最大公约数的解法

求最大公约数的解法

---

# 解法描述
计算两个数的最大公约数的不同解法，包括：
a. 欧几里得算法 gcd1，更详细描述可以参见维基欧几里得算法。

b. 计算gcd(m, n)的连续整数检测算法gcd2。

c. 中学里的计算方法gcd3, 相对最复杂的解法，不过计算结果当然是有效的，正确。算法逻辑描述如下：

1 找到m的所有质数prime1；
2 找到n的所有质数prime2；
3 从prime1和prime2中找出所有的公因数com_prime。
注意：如果p是其中一个公因数，而且在prime1和prime2中分别出现Pm，Pn次那么应该将p重复min{Pm, Pn}次；
4 将com_prime的所有质因数相乘，结果即m, n最大公约数。

……（gcd3解法O_o 够折腾的求解过程吧。） ……


以上三者不同解法的效率也不同，比较情况为：gcd1 > gcd2 > gcd3 。

# 代码示例


int gcd1(int m, int n)
{
    assert (m>0 && n>0);
    if (m < n)
std::swap(m, n);
    while (0 !=n) {
        int r = m % n;
        m = n;
        n = r;
    }
    return m;
}

int gcd2(int m, int n)

{

    assert (m>0 && n>0);

    int min = (m > n ? n : m);

    for (; ; --min) {

        if (0 == m % min && 0 == n % min)

            break;

    }

    return min;

}

int gcd3(int m, int n)

{ 

... 代码繁多，在此略 ...

}

# 附
> 完整代码示例，参见github。

（完）