21xrx.com
2025-03-27 01:08:21 Thursday
文章检索 我的文章 写文章
C++求最大公约数的代码
2023-06-25 02:01:05 深夜i     10     0
C++ 最大公约数 代码

在算法编程中，求最大公约数是一个常见的问题。C++提供了多种方法来实现。下面是使用辗转相除法求解最大公约数的C++代码示例。

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
  if(b == 0) return a;
  else return gcd(b, a % b);
}
int main()
{
  int a, b;
  cout << "Enter two positive integers: ";
  cin >> a >> b;
  int result = gcd(a, b);
  cout << "The GCD of " << a << " and " << b << " is " << result;
  return 0;
}

在这里，我们使用递归和取模运算实现了辗转相除法来求最大公约数。如果b为0，那么a就是最大公约数。如果b不为0，则计算a与b的余数r，然后将b赋值为原来的a，将r赋值为新的b，递归调用gcd函数。以此类推，直到b等于0为止。

以上C++代码可以实现求两个正整数的最大公约数。如果需要求解多个数的最大公约数，可以将其分解成两个数的最大公约数的连续求解，一直到最后一个数。辗转相除法是计算最大公约数的常用方法，也可以使用更高级的方法来实现算法的优化。在编程中，了解各种算法和方法的优缺点，有助于提高程序的效率和性能。

  
  

评论区