在C++中求最小公倍数的方法

在C++中，求最小公倍数的方法主要有两种，一种是使用辗转相除法，一种是使用穷举法。

辗转相除法

辗转相除法是一种较为常用的求最小公倍数的方法，它的基本思想是：两个数的最小公倍数等于这两个数的乘积除以它们的最大公约数。

下面介绍一下辗转相除法的使用方法：

• 计算出两个数的最大公约数，可以使用辗转相除法，也可以使用其他方法；
• 计算出它们的乘积；
• 将这个乘积除以它们的最大公约数，就得到了它们的最小公倍数。

int gcd(int a, int b)
{
    int t;
    while(b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

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

穷举法

穷举法是另一种求最小公倍数的方法，它的基本思想是：从两个数的最小值开始，依次穷举，直到找到两个数的公倍数。

下面介绍一下穷举法的使用方法：

• 计算出两个数的最小值；
• 从最小值开始，依次穷举，直到找到两个数的公倍数，这个数就是它们的最小公倍数。

int lcm(int a, int b)
{
    int min = a < b ? a : b;
    int max = a > b ? a : b;
    int i = min;
    while(i % max != 0)
    {
        i += min;
    }
    return i;
}