C++求多个数的最大公约数 |21xrx.com

C++求多个数的最大公约数

2023-07-04 07:26:48 深夜i -- --

C++ 多个数最大公约数

在C++编程中，经常会用到求多个数的最大公约数的函数。求多个数的最大公约数，可以使用辗转相除法或欧几里得算法。接下来，我们将介绍使用辗转相除法来求多个数的最大公约数的方法。

辗转相除法，也称为欧几里得算法，是一种求最大公约数的简单有效算法。其基本思想是：用较小数（被除数）除以较大数（除数），接着用上一次的余数作为新的被除数，上一次的除数作为新的除数，依次递归，直到余数为0。这时，最后的除数即为所求的最大公约数。

下面是使用辗转相除法来求多个数的最大公约数的C++代码：


#include <iostream>
using namespace std;
// 求最大公约数
int gcd(int a, int b)
{
  if (a % b == 0)
    return b;
  else
    return gcd(b, a % b);
}
// 求多个数的最大公约数
int gcd(int *arr, int n)
{
  int ans = arr[0];
  for (int i = 1; i < n; i++)
  {
    ans = gcd(ans, arr[i]);
    if (ans == 1)
      break;
  }
  return ans;
}
int main()
{
  int arr[] = 48;
  int n = sizeof(arr) / sizeof(arr[0]);
  int ans = gcd(arr, n);
  cout << "最大公约数为：" << ans << endl;
  return 0;
}

在上面的代码中，我们首先定义了一个求最大公约数的函数gcd()，然后再定义了一个求多个数的最大公约数的函数gcd(int *arr，int n)。这个函数接收一个整型数组和数组的长度作为参数，通过调用gcd()函数来求出多个数的最大公约数。

最后，我们在主函数中定义一个整型数组，填入多个数字，并通过调用gcd()函数来求出这些数字的最大公约数。运行程序，显示结果为：最大公约数为：12。

通过这个例子，我们可以看出使用辗转相除法来求多个数的最大公约数非常简单，只需要将多个数依次传入gcd()函数即可。

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

下一篇: 如何查看C++文件的位置

评论区

()

相似文章