C++求两个正整数的最大公约数 |21xrx.com

C++求两个正整数的最大公约数

2023-07-10 03:58:05 深夜i -- --

C++ 正整数最大公约数

在计算机科学和数学中，最大公约数（Greatest Common Divisor，简称GCD）是指两个或多个整数的最大公约数。在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 num1, num2;
  cout << "Enter two positive integers: ";
  cin >> num1 >> num2;
  int result = gcd(num1, num2);
  cout << "The GCD of " << num1 << " and " << num2 << " is " << result << endl;
  
  return 0;
}

在此示例中，我们定义了一个名为gcd的函数来计算两个整数的最大公约数。使用递归算法，该函数将b作为区间[a，b]的余数，并重复此过程，直到b为0时停止并返回a。

接着在main函数中，我们要求用户输入两个正整数，并将它们传递给gcd函数。最后将结果输出至控制台。

这是一个简单而实用的C++程序示例，可供编程新手学习和掌握如何使用欧几里德算法来计算两个整数的最大公约数。

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

下一篇: C++能否不使用头文件？

评论区

()

相似文章