之前一直都不是用的辗转相除求公约数,上次测试吃了点小亏,今天刷oj看到一个题,于是百度了下,现在记录一下。

辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

算法用递归实现很简单。

比如 求a,b的最大公约数(a>=b).过程如下:

t = a % b,如果t=0,结束,最大公约数为b,否则继续
a = b,b = t.
t = a % b,如果t=0,结束,最大公约数为b,否则继续
……
直到t=0,返回的值就是最大公约数了, 最小公倍数 则直接用a*b/最大公约数就可以了

代码如下:
递归实现:

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

循环实现

    int t = 1;
    while (t != 0)
    {
        t = a % b;
        a = b;
        b = t;
    }
    cout << a << endl;//a就是最最大公约数
最后修改:2019 年 06 月 26 日 10 : 10 PM
如果觉得我的文章对你有用,请随意赞赏