C++求两个数的最大公约数和最小公倍数 |21xrx.com

2023-06-24 09:36:45 深夜i -- --

C++ 最大公约数最小公倍数求解

在数学中，最大公约数和最小公倍数是非常基础和重要的概念。在计算机编程中，求两个数的最大公约数和最小公倍数也是经常出现的问题。C++作为一门高级编程语言，自然也有相应的函数来计算最大公约数和最小公倍数。

下面介绍两种常用的方法。

方法一：辗转相除法

辗转相除法，也称为欧几里得算法，是求最大公约数的基本方法之一。具体步骤如下：

1. 用较大数 mod 较小数，将得到的余数作为新的较大数，原较小数作为新的较小数；

2. 重复以上步骤，直到较小数为 0，返回较大数即为最大公约数。

代码如下：


int gcd(int a, int b) {
  if (b == 0)
    return a;
   else {
    return gcd(b, a % b);
  }
}

方法二：最大公倍数与最小公约数的关系

假设 a 和 b 分别是两个整数，它们的最大公约数是 x，最小公倍数是 y。则有以下关系式：

x * y = a * b

根据上式就可以求得 y 的值。

代码如下：


int lcm(int a, int b) {
  return a * b / gcd(a, b);
}

以上就是求两个数的最大公约数和最小公倍数的两种方法。使用这两种方法可以方便地在 C++ 中计算两个数的最大公约数和最小公倍数。

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

下一篇: C++11的类内初始化技巧

()

相似文章