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

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

2023-07-07 11:23:00 深夜i -- --

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

C++ 求解两个正整数的最大公约数是程序员在编写程序时经常需要用到的功能之一。在这篇文章中，我们将介绍如何使用 C++ 语言来实现这一功能。

最大公约数，也称为最大公因数，是指能够同时被两个或多个整数整除的最大的正整数。为了求解两个正整数的最大公约数，我们需要使用欧几里得算法，也称为辗转相除法。

欧几里得算法的基本思想是，对于两个正整数 a 和 b（a>b），可以进行如下的一系列除法操作：

a = q1 * b + r1

b = q2 * r1 + r2

r1 = q3 * r2 + r3

.....

rn-2 = qn * rn-1 + rn

其中，rn 就是最大公约数，也就是我们所需要求解的答案。可以用递归函数来实现这个算法。具体实现如下：


#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 = 16, b = 24;
  int g = gcd(a, b);
  cout << "gcd(" << a << "," << b << ")=" << g << endl;
  return 0;
}

在这个程序中，我们定义了一个名为 gcd 的递归函数。当输入的第二个数为 0 时，程序就会返回第一个数，也就是最大公约数。如果第二个数不是 0，那么程序将会继续调用自身，每次将第二个数作为被除数，第一个数对第二个数取余的结果作为除数，直到第二个数变成 0。

在这个例子中，我们使用了两个正整数 16 和 24。程序将输出它们的最大公约数 8。

总结起来，C++ 求解两个正整数的最大公约数只需要使用欧几里得算法，通过递归的方式不断求解余数即可。这是一个非常简单和实用的算法，应该是每个程序员都应该掌握的基础知识。

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

下一篇: DVC++初学者如何使用？

评论区

()

相似文章