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

欧几里得算法又称辗转相除法，描述如下：

　　两个整数的最大公约数与 其中较小的数 和 较大的数与较小数的余数 的最大公约数相同。

　　其中我们需要知道，零与任何数的最大公约数为其中的那个非零数。

 

所以我们可以设计如下算法：

#include <iostream>

using namespace std;

int euclid(int m, int n);

int main()
{
    int m, n;
    int result;
    cout << "Please enter two number:" << endl;
    cin >> m >> n;
    result = euclid(m, n);
    cout << "Result is: " << result;

    return 0;
}

int euclid(int m, int n)
{
    int t;
    while (m != 0)
    {
        t = m;
        m = n % m;
        n = t;
    }
    return n;
}