在 C++ 中找到给定数组元素阶乘的最大公约数

假设我们有一个包含 N 个元素的数组 A，我们必须找到该数组所有元素阶乘的最大公约数。假设元素为 {3, 4, 8, 6} 阶乘的最大公约数为 6。接下来我们将看到这个技巧。因为两个数的最大公约数是能同时整除这两个数的最大数，所以两个数的阶乘的最大公约数是最小数的阶乘值本身。因此，3! 和 5! 的最大公约数是 3! = 6。

示例

 现场演示

#include <iostream>
using namespace std;
long fact(int n){
   if(n <= 1)
      return 1;
   return n * fact(n-1);
}
int gcd(int arr[], int n) {
   int min = arr[0];
   for (int i = 1; i < n; i++) {
      if(min > arr[i])
         min = arr[i];
   }
   return fact(min);
}
int main() {
   int arr[] = {3, 4, 8, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "GCD: "<< gcd(arr, n);
}

输出

GCD: 6

更新于:2019 年 10 月 21 日

329 次浏览

启动你的 职业

完成课程获得认证

开始
广告