C++求最大公因数和最小公倍数的代码 |21xrx.com

2023-06-27 04:51:18 深夜i -- --

C++ 最大公因数最小公倍数代码

C++是一门强大的编程语言，它提供了许多方便的算法。其中，求最大公因数和最小公倍数是编程中经常会用到的问题。本文将介绍在C++中如何求最大公因数和最小公倍数的代码。

首先，我们来看如何求最大公因数。在C++中，可以使用辗转相减法、欧几里得算法（辗转相除法）或更相减损术（更相减损术），这里我们以欧几里得算法为例。

欧几里得算法的原理是：计算两个数的余数，然后用较小的数去除余数，再用除数和余数继续操作，一直到余数为0。此时，除数就是最大公因数。

下面是示例代码：


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

在代码中，我们首先判断a是否为0，如果是，那么最大公因数就是b。否则，我们使用b对a取模，并将结果递归地传递给a和b%a。

接下来，我们来看如何求最小公倍数。

最小公倍数定义为两个或多个整数的公共倍数中的最小值。可以用辗转相减法、欧几里得算法和质因数分解法来求最小公倍数，在这里我们使用辗转相乘法。

辗转相乘法的原理是：将两个数先求出最大公因数，然后将这两个数相乘，再除以最大公因数，得到的结果就是最小公倍数。

下面是示例代码：


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

在代码中，我们先调用前面编写的gcd函数求出a和b的最大公因数，然后将a和b相乘，再除以最大公因数。

以上就是在C++中求最大公因数和最小公倍数的代码。无论是辗转相除法、欧几里得算法、质因数分解法还是辗转相乘法，都需要经过实践和掌握才能灵活运用，希望大家多多练习。

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

下一篇: C++能够解决哪些问题？

()

相似文章