C++实现辗转相除法求最小公倍数 |21xrx.com

2023-07-04 22:23:50 深夜i -- --

C++ 辗转相除法最小公倍数

辗转相除法是计算两个数最大公约数的一种常见方法。但是，它也可以用于求两个数的最小公倍数。本文将介绍如何使用C++实现辗转相除法求最小公倍数。

首先，让我们看看最小公倍数的定义。如果a和b是两个正整数，那么它们的最小公倍数是可以被a和b整除的最小正整数。例如，5和6的最小公倍数是30，因为它是5和6的第一个公共倍数。我们可以使用辗转相除法来计算两个数的最小公倍数。

下面是C++代码实现：


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);
}

上面的代码中，我们首先使用辗转相除法计算a和b的最大公约数。然后，我们将a和b相乘，并除以它们的最大公约数来得到最小公倍数。注意，我们必须将a和b相乘后再除以它们的最大公约数，否则结果可能会超出整数范围。

让我们看看一个例子，假设我们需要求18和24的最小公倍数。首先，我们使用辗转相除法计算它们的最大公约数：


gcd(18, 24) => gcd(24, 18 % 24) => gcd(24, 18) => gcd(18, 24 % 18) => gcd(18, 6) => gcd(6, 18 % 6) => gcd(6, 0) => 6

可以看到，18和24的最大公约数是6。然后，我们使用下面的代码计算最小公倍数：


lcm(18, 24) => (18 * 24) / 6 => 72

因此，18和24的最小公倍数是72。

在实际编程中，我们可能需要计算多个数的最小公倍数。我们可以使用上述代码中的lcm函数来计算任意两个数的最小公倍数。如果我们有n个数，我们可以将它们两两求最小公倍数，然后再继续将结果两两求最小公倍数，直到最后只剩下一个数，这个数就是它们的最小公倍数。这个过程称为“两两求最小公倍数法”。

最后，我们需要注意的一点是，C++标准库中也有提供求最小公倍数的函数std::lcm。因此，在编写程序时，我们应该优先使用标准库中的函数。

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

下一篇: C++中逗号运算符的规则解析

()

相似文章