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

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

2023-06-29 19:53:39 深夜i -- --

C++ 求N个数最大公约数

在C++中，要求N个数的最大公约数是一个常见的问题。最大公约数是指能够同时被所有数字整除的最大整数。

首先，我们需要知道一个数学公式，即“欧几里得算法”。这个算法一般用于求两个数的最大公约数，但也可以拓展到求N个数的最大公约数。

欧几里得算法是基于如下原理：两个数的最大公约数等于其中较小的那个数和两数之差的最大公约数。比如，如果我们想找出56和42的最大公约数，我们可以先找出56和42的余数，也就是14和42。然后，我们再找出14和42的余数，即14和28。最后，我们再次找出14和28的余数，这次是14和0。因为14整除56和42，所以14是它们的最大公约数。

那么，我们如何将欧几里得算法应用到N个数上呢？其实很简单，只需要对这N个数进行连续的求余运算即可。比如，我们要求出12、18和24的最大公约数，可以按照如下方式进行计算：

1. 18%12=6，24%18=6

2. 12%6=0，18%6=0，24%6=0

因为6可以同时被12、18和24整除，所以6是它们的最大公约数。

让我们来看一下如何在C++中实现这个算法。我们可以使用一个for循环，遍历所有的数字并计算它们的余数。最后，我们将所有余数复制到一个新数组中，并使用欧几里得算法求出它们的最大公约数。下面是代码示例：


#include <iostream>
using namespace std;
int main() {
  int n, i, j, gcd, *nums;
  cin >> n;
  nums = new int[n];
  for (i = 0; i < n; i++) {
    cin >> nums[i];
  }
  gcd = nums[0];
  for (i = 1; i < n; i++) {
    j = nums[i];
    while (j > 0)
      int temp = j;
      j = gcd % j;
      gcd = temp;
    
  }
  cout << "The GCD is " << gcd << endl;
  delete[] nums;
  return 0;
}

以上是求N个数的最大公约数的全部内容。实现这个算法需要一点数学知识和一些C++编程技巧。如果你想学习更多C++编程知识，可以逐步掌握更多相关技术和知识点。

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

下一篇: 原因及解决方法

评论区

()

相似文章