C++如何高效求取最大公约数

求取最大公约数是数学中的一个重要问题，在计算机科学中也有很多应用。在C++中，可以使用辗转相除法来高效求取最大公约数。

辗转相除法

辗转相除法（又称欧几里德算法）是一种求最大公约数的算法，它可以用于求两个整数的最大公约数。该算法的基本思想是：用较大的数除以较小的数，再用除数除以出现的余数，如此重复，直到余数为0，此时除数就是最大公约数。

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

上面的代码是一个使用C++实现辗转相除法的简单示例，函数gcd()接受两个参数a和b，返回它们的最大公约数。

使用示例

• 求取最大公约数：

  int gcd = gcd(24, 18); // gcd = 6

• 求取最小公倍数：

  int lcm = (24 * 18) / gcd; // lcm = 72

从上面的示例可以看出，通过辗转相除法可以高效求取最大公约数，并且可以利用最大公约数求得最小公倍数。