C++中求最大公因数和最小公倍数的方法 |21xrx.com

2023-07-11 07:47:35 深夜i -- --

C++ 最大公因数最小公倍数方法

在C++编程语言中，求最大公因数和最小公倍数是一项重要的数学运算。最大公因数和最小公倍数分别用于对两个或多个整数进行约简和扩大。下面将介绍在C++中求最大公因数和最小公倍数的方法。

求最大公因数的方法

求最大公因数的方法有多种。其中最常用的方法是辗转相减法和辗转相除法。

辗转相减法的基本思想是：若两个正整数a和b，且a>b，则a和b的最大公因数等于a-b和b的最大公因数。因此，我们可以用a和b的差替换掉较大的那个整数，直到两个整数相等或其中一个为0。此时，非零的那个整数就是最大公因数。

代码如下：


int gcd(int a, int b) {
  while (a != b) {
    if (a > b)
      a -= b;
     else
      b -= a;
    
  }
  return a;
}

辗转相除法的基本思想是：若两个正整数a和b，且a>b，则a和b的最大公因数等于b和a mod b的最大公因数。因此，我们可以用b和a mod b替换掉a和b，重复执行这个操作，直到b为0。此时，非零的那个整数就是最大公因数。

代码如下：


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

以上两种方法都可以求出最大公因数，根据实际情况选择使用。但是，辗转相减法在较大的整数时会有效率问题，因此建议优先使用辗转相除法。

求最小公倍数的方法

求最小公倍数的方法也有多种。其中最常用的方法是先求出最大公因数，然后通过最大公因数求出最小公倍数。

最小公倍数等于两个数的积除以它们的最大公因数，即：


lcm(a, b) = a * b / gcd(a, b)

因此，我们只需要先求出最大公因数，然后用它来计算最小公倍数即可。

代码如下：


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

总结

在C++中，求最大公因数和最小公倍数是一项基础的数学运算。本文介绍了两种求最大公因数的方法，分别是辗转相减法和辗转相除法。同时，还介绍了通过最大公因数求最小公倍数的方法。根据实际情况选择合适的方法，可以提高程序的执行效率。

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

下一篇: C++编程：给定某股票每日的报价

()

相似文章