C++求最大公约数和最小公倍数的实现方法

一、背景介绍

在数学中，最大公约数（Greatest Common Divisor, 简称GCD）和最小公倍数（Least Common Multiple, 简称LCM）是两个非常重要的概念。

最大公约数是指两个或多个整数共有约数中最大的一个，例如 8 和 12 的最大公约数是 4。

最小公倍数是指两个或多个整数公有的倍数中最小的一个，例如 4 和 6 的最小公倍数是 12。

获得最大公约数和最小公倍数有很多方法，本文将介绍用C++实现的方法。

二、辗转相除法

辗转相除法，又称欧几里得算法，是求最大公约数的经典方法。该算法基于如下性质：两个正整数a和b（a>b）的最大公约数等于a除以b的余数c和b之间的最大公约数。

代码实现如下：

int gcd(int a, int b)
{
    if (a < b)  //保证a大于b
        swap(a, b);
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

对于求最小公倍数，可以先使用辗转相除法求出最大公约数，然后套用以下公式：

最小公倍数 = a×b / 最大公约数

代码实现如下：

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

三、更相减损术

更相减损术是另一种求最大公约数的方法。该算法基于如下性质：两个正整数a和b（a>b）的最大公约数等于a-b的差值c和较小数b之间的最大公约数。

代码实现如下：

int gcd(int a, int b)
{
    if (a < b)
        swap(a, b);
    while (a - b != b)  //循环终止条件为 a-b=b
    {
        int temp = a - b;
        a = max(b, temp);
        b = min(b, temp);
    }
    return b;
}

但是，这种算法的效率远低于辗转相除法，因此不常用。

四、更优秀的实现

虽然辗转相除法已经很优秀了，但是还是可以进一步优化。

一种优化的方法是 Stein算法，结合了更相减损术和位移运算的思想。该算法在计算机上运行的效率比辗转相除法要高，因为位移运算比除法运算要快。

代码实现如下：

int gcd(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    int shift;
    for (shift = 0; ((a | b) & 1) == 0; ++shift)
    {
        a >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0)  a >>= 1;
    do {
        while ((b & 1) == 0)  b >>= 1;
        if (a > b)  swap(a, b);
        b -= a;
    } while (b != 0);
    return a << shift;
}

对于求最小公倍数，也可以使用 Stein算法。代码实现如下：

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

五、总结

求最大公约数和最小公倍数是我们在编程中经常会碰到的问题，本文主要介绍了辗转相除法、更相减损术和 Stein算法三种方法，其中辗转相除法是应用最广泛的。

需要注意的是，在使用求最小公倍数公式时，由于乘法运算的结果可能超出 int 类型的范围，因此需要使用更高精度的数据类型，如 long long。

希望本文能够对读者有所帮助。