如何在C++中求解三个数的最大公因数 |21xrx.com

如何在C++中求解三个数的最大公因数

2023-07-11 22:40:33 深夜i -- --

C++ 最大公因数求解三个数

在C++中，有多种方法可以求解三个数的最大公因数。下面介绍两种常见的方法。

方法一：暴力枚举法

暴力枚举法是最简单的求解三个数最大公因数的方法之一。该方法的基本思想是从3个数中最小的开始，依次进行递减的枚举并测试每个数是否是三个数的公因数。如果是，则将该数作为当前的最大公因数，否则继续枚举。

具体实现如下：


#include <iostream>
using namespace std;
int gcd(int a, int b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
int main(){
  int a, b, c;
  cout << "请输入三个整数: ";
  cin >> a >> b >> c;
  int min_num = min(a, min(b, c));
  for(int i = min_num; i > 0; i--){
    if(a % i == 0 && b % i == 0 && c % i == 0)
      cout << "三个数的最大公因数为：" << i << endl;
      break;
    
  }
  return 0;
}

该算法的时间复杂度为$O(min(a,b,c))$。

方法二：辗转相除法

辗转相除法，也称欧几里得算法，是一种求最大公因数的经典算法。基本思想是利用两个数的余数来求它们的最大公因数。

具体步骤如下：

- 用较大的数除以较小的数，得到一个余数。

- 如果余数为0，则较小的数就是两个数的最大公因数。

- 如果余数不为0，则让较小的数等于余数，较大的数等于之前的较小的数，然后重复步骤1。

这个算法可以推广至多个数的情况。一个通用的方法是，先求出前两个数的最大公因数，然后再将其与第三个数求最大公因数，以此类推，直到最后一个数。

具体实现如下：


#include <iostream>
using namespace std;
int gcd(int a, int b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
int gcd(int* nums, int len){
  int res = nums[0];
  for(int i = 1; i < len; i++){
    res = gcd(res, nums[i]);
  }
  return res;
}
int main(){
  int a, b, c;
  cout << "请输入三个整数: ";
  cin >> a >> b >> c;
  int nums[] = b;
  int len = sizeof(nums) / sizeof(nums[0]);
  int res = gcd(nums, len);
  cout << "三个数的最大公因数为：" << res << endl;
  return 0;
}

该算法的时间复杂度为$O(log(min(a,b,c))$。

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

下一篇: "Mac电脑能否运行C++程序？"

评论区

()

相似文章