如何用C++求两个数的最大公约数和最小公倍数

我们可以使用以下两种方法求出两个数的最大公约数（Greatest Common Divisor, GCD）和最小公倍数（Least Common Multiple, LCM）。

方法一：欧几里得算法

欧几里得算法又称辗转相除法，基本原理是：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

对于两个正整数a、b（a>b）我们有：

$gcd(a,b)=gcd(b,a\mod b)$

当$a\mod b$等于0时，返回b。

下面是C++代码实现：

#include <iostream>
using namespace std;

// 欧几里得算法求最大公约数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b , a % b); // 递归调用
}

// 最小公倍数等于两数之积除以它们的最大公约数
int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

int main()
{
    int a, b;
    cout << "Enter two positive integers:" << endl;
    cin >> a >> b;
    cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
    cout << "LCM(" << a << ", " << b << ") = " << lcm(a, b) << endl;
    return 0;
}

以下是两个示例：

1. 将a设为98，b设为63。执行程序后，结果应该为：GCD(98, 63) = 7，LCM(98, 63) = 2184。

2. 将a设为45，b设为30。执行程序后，结果应该为：GCD(45, 30) = 15，LCM(45, 30) = 90。

方法二：枚举法

枚举法是一种简单易懂但效率低下的求解最大公约数和最小公倍数的方法。具体步骤如下：

1. 设a、b是待求的两个正整数。

2. 对它们进行因数分解，记作：

​ a=$m_1p_1^{q_1}m_2p_2^{q_2} \cdots m_np_n^{q_n}$

​ b=$n_1r_1^{s_1}n_2r_2^{s_2} \cdots n_mr_m^{s_m}$

1. 其中，$m_1, m_2, \cdots , m_n$ 和 $n_1, n_2, \cdots , n_m$ 是不同的质数，$p_1, p_2, \cdots , p_n$ 和 $r_1, r_2, \cdots , r_m$ 是它们的指数。

2. 则：

​ gcd(a,b)=$ltp_{m_j} ^ {min(q_j,s_j)}$

​ lcm(a,b)=$lt{p_{m_j}}^{max(q_j,s_j)}$

下面是C++代码实现：

#include <iostream>
using namespace std;

// 判断一个数是否为质数
bool is_prime(int x)
{
    if (x <= 1)
        return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}

// 枚举法求最大公约数
int gcd(int a, int b)
{
    int g = 1;
    for (int d = 2; d <= a && d <= b; d++)
        if (a % d == 0 && b % d == 0)
            g = d;
    return g;
}

// 枚举法求最小公倍数
int lcm(int a, int b)
{
    int l = 1;
    for (int p = 2; p <= a || p <= b; p++)
    {
        if (is_prime(p))
        {
            int ap = 0, bp = 0;
            while (a % p == 0)
            {
                a /= p;
                ap++;
            }
            while (b % p == 0)
            {
                b /= p;
                bp++;
            }
            int cp = max(ap, bp);
            while (cp-- > 0)
                l *= p;
        }
    }
    return l;
}

int main()
{
    int a, b;
    cout << "Enter two positive integers:" << endl;
    cin >> a >> b;
    cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
    cout << "LCM(" << a << ", " << b << ") = " << lcm(a, b) << endl;
    return 0;
}

以下是两个示例：

1. 将a设为98，b设为63。执行程序后，结果应该为：GCD(98, 63) = 7，LCM(98, 63) = 2184。

2. 将a设为45，b设为30。执行程序后，结果应该为：GCD(45, 30) = 15，LCM(45, 30) = 90。