C++如何计算最小公倍数和最大公约数？ |21xrx.com

C++如何计算最小公倍数和最大公约数？

2023-07-01 01:43:12 深夜i -- --

C++ 计算最小公倍数最大公约数

C++是一种较为常用的编程语言，也是计算最小公倍数和最大公约数的一种常用语言。在C++中，可以使用循环或递归来计算最大公约数和最小公倍数。下面我们来看看具体的实现方法。

计算最大公约数：

1. 使用欧几里得算法

欧几里得算法，也称辗转相除法，是一种计算最大公约数的常用方法。其思想是不断地用较小数去除较大数，直到余数为零，此时较小数即为最大公约数。

C++代码实现：

int gcd(int a, int b) {

if (a == 0)

return b;

return gcd(b % a, a);

}

2. 使用更相减损算法

更相减损算法是另一种计算最大公约数的方法。其思想是先找出两个数的差，然后不断用较小的数去减较大的数，直到两数相等，此时就找到了最大公约数。

C++代码实现：

int gcd(int a, int b) {

while (a != b) {

if (a > b)

a -= b;

else

b -= a;

}

return a;

}

计算最小公倍数：

1. 使用辗转相除法

利用最大公约数，可以很容易地计算出最小公倍数。最小公倍数等于两数相乘除以最大公约数。

C++代码实现：

int lcm(int a, int b) {

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

}

2. 使用枚举法

如果数据量不大的话，可以使用枚举法来计算最小公倍数。枚举所有可能的数，直到找到一个既是a的倍数又是b的倍数的数，即为最小公倍数。

C++代码实现：

int lcm(int a, int b) {

int max = (a > b) ? a : b;

while (true) {

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

return max;

max++;

}

总结：

无论采用什么方法，C++都可以很方便地计算最大公约数和最小公倍数。对于较大的数据，欧几里得算法的效率比较高。而对于数据量小的情况，枚举法可以很好地满足需求。

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

下一篇: C++如何判断输入数据的类型？

评论区

()

相似文章