C++如何求最大公因数和最小公倍数 |21xrx.com

C++如何求最大公因数和最小公倍数

2023-07-02 01:19:55 深夜i 13 0

C++ 最大公因数最小公倍数算法循环

C++是一种常用的计算机编程语言，方便灵活，使用广泛。在数学计算中，求最大公因数和最小公倍数也是常见的问题，下面介绍如何用C++来解决这两个问题。

求最大公因数的方法是辗转相除法，也称欧几里德算法。该算法基于以下原则：对于任意两个正整数a和b（a>b），它们的最大公因数等于b与a%b的最大公因数，即gcd(a,b) = gcd(b,a%b)。这个过程可以反复进行，直到b为0时，a就是最大公因数。以下是C++代码实现：

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

接下来是求最小公倍数的方法。最小公倍数是指n个正整数中，能够被每个正整数整除的最小数，记为lcm(a1,a2,...,an）。常见的做法是求出这n个数的最大公因数，然后用它们的乘积除以最大公因数就可以求出最小公倍数，即lcm(a1,a2,...,an)=a1*a2*...*an/gcd(a1,a2,...,an)。以下是C++代码实现：

int lcm(int a, int b) {
  return a * b / gcd(a, b);
}
int lcm(vector<int>& nums) {
  int ans = 1;
  for (int i = 0; i < nums.size(); i++) {
    ans = lcm(ans, nums[i]);
  }
  return ans;
}

在上面代码中，我们用了一个可变长度的整数向量nums表示n个正整数，依次求它们的最小公倍数并对它们进行累乘求积，最后除以它们的最大公因数就可以得到所求的最小公倍数。

以上就是如何用C++语言来求解最大公因数和最小公倍数的方法，读者可以根据需要加以应用和修改，以适应具体的编程场景和任务需求。

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

下一篇: C++11标准库时间模块

评论区

相似文章