c++中如何计算两个数的最小公倍数_c++最小公倍数计算方法-C++-PHP中文网

c++中如何计算两个数的最小公倍数_c++最小公倍数计算方法

裘德小鎮的故事

发布： 2025-10-04 17:21:03

原创

801人浏览过

<p>最小公倍数可通过最大公约数计算，公式为LCM(a, b) = a / GCD(a, b) * b，推荐手动实现GCD并使用long long类型防溢出。</p>

c++中如何计算两个数的最小公倍数_c++最小公倍数计算方法

在C++中计算两个数的最小公倍数（LCM，Least Common Multiple），通常借助它们的最大公约数（GCD，Greatest Common Divisor）来实现。因为两个数的乘积等于它们的最大公约数与最小公倍数的乘积：

a × b = GCD(a, b) × LCM(a, b)

因此，可以通过以下公式求最小公倍数：

LCM(a, b) = (a × b) / GCD(a, b)

立即学习“C++免费学习笔记（深入）”；

下面介绍具体实现方法。

1. 使用__gcd()内置函数（快速实现）

在C++17之前，GCC编译器提供了__gcd()函数用于计算最大公约数，可以简化代码：

#include <iostream>
#include <algorithm>  // __gcd()在此头文件中
using namespace std;
<p>int lcm(int a, int b) {
return (a * b) / __gcd(a, b);
}</p><p>int main() {
int x = 12, y = 18;
cout << "LCM of " << x << " and " << y << " is " << lcm(x, y) << endl;
return 0;
}

登录后复制

注意：__gcd()不是标准C++函数，依赖编译器，在某些环境下可能不可用。

办公小浣熊

办公小浣熊是基于商汤大语言模型的原生数据分析产品，

查看详情

2. 手动实现GCD（推荐方式）

使用欧几里得算法（辗转相除法）手动实现GCD，更加通用和可移植：

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
<p>int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}

登录后复制

这个版本不依赖编译器扩展，适用于所有标准C++环境。

3. 避免整数溢出的改进写法

直接计算a * b可能导致整数溢出。更安全的方式是先除后乘：

int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 先除后乘，减少溢出风险
}

登录后复制

因为a一定能被gcd(a, b)整除，所以这样写结果正确且更安全。

4. 支持更大数值类型

如果输入可能是较大的数，建议使用long long类型：

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
<p>long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}

登录后复制

基本上就这些。只要掌握GCD与LCM的关系，再用欧几里得算法实现，就能稳定计算最小公倍数。推荐使用手动实现GCD的方式，避免依赖非标准函数，同时注意溢出问题。基本上就这些。

以上就是c++++中如何计算两个数的最小公倍数_c++最小公倍数计算方法的详细内容，更多请关注php中文网其它相关文章！