C++求最小公倍数：有哪些方法？公式是什么？ |21xrx.com

C++求最小公倍数：有哪些方法？公式是什么？

2023-06-22 11:09:39 深夜i -- --

C++ 最小公倍数方法公式

在C++中，求最小公倍数有多种方法。其中比较常用的有以下几种：

方法1：暴力法

暴力法是一种最简单直接的方法，即从2开始递增枚举每个数，分别判断是否是两个数的公倍数，如果是则返回该数。

C++代码实现：

int LCM(int a, int b) {

int ans = 0;

for(int i = 2; ; i++) {

if(i % a == 0 && i % b == 0)

ans = i;

break;

}

return ans;

}

方法2：辗转相除法

辗转相除法是一种判断两个数的最大公约数的常用方法，其中求最小公倍数就是利用最大公约数来求得。公式如下：

最小公倍数 = 两数的积 ÷ 最大公约数

C++代码实现：

int GCD(int a, int b) {

return b == 0 ? a : GCD(b, a % b);

}

int LCM(int a, int b) {

return a * b / GCD(a, b);

}

方法3：质因数分解法

质因数分解法是一种将一个数分解成质数的乘积的方法，根据两个数的质因数分解式，求最小公倍数的质因数分解式为：

最小公倍数 = 两数的所有质因数的乘积（含重复的质数）

C++代码实现：

int LCM(int a, int b) {

int ans = 1;

for(int i = 2; i <= max(a, b); i++) {

int cnt1 = 0, cnt2 = 0;

while(a % i == 0) {

cnt1++;

a /= i;

}

while(b % i == 0) {

cnt2++;

b /= i;

}

ans *= pow(i, max(cnt1, cnt2));

}

return ans;

}

综上所述，C++求最小公倍数有多种方法，每种方法都有其特点和适用范围，程序员可以根据实际需求选择合适的方法。

上一篇: idea打包java可执行jar包

下一篇: 如何在Dev-C++中创建C语言项目？

评论区

()

相似文章