C++实现判断两个数互质的算法 |21xrx.com

C++实现判断两个数互质的算法

2023-07-10 00:19:21 深夜i -- --

C++ 两个数互质算法

C++ 实现判断两个数互质的算法

什么是互质？

当两个数 A 和 B 的最大公约数为 1 时，称 A 和 B 为互质（或互素）的。例如，2 和 3 是互质的，因为它们的最大公约数是 1，而 8 和 12 不是互质的，因为它们的最大公约数是 4。

算法

为了判断给定的两个整数是否互质，可以使用欧几里得算法(辗转相除法)来找到它们的最大公约数。这个算法的步骤如下：

1. 判断 A 是否能够被 B 整除。如果是，那么返回 B，否则继续进行下一步。

2. 计算 A % B （A 对 B 取余的结果），令结果为 R。

3. 将 B 赋值为 A，并将 A 赋值为 R。

4. 重复步骤 1~3，直到 R 为 0。

最后，如果 A=1（即它们的最大公约数为 1），则认为这两个数是互质的。

使用 C++ 实现

下面是使用 C++ 实现判断两个数是否互质的函数：


#include<iostream>
using namespace std;
int gcd(int a, int b) {
  if (a % b == 0)
    return b;
   else {
    return gcd(b, a % b);
  }
}
bool isCoprime(int a, int b) {
  return gcd(a, b) == 1;
}
int main() {
  int a, b;
  cout << "输入两个整数，以空格分隔：";
  cin >> a >> b;
  if (isCoprime(a, b))
    cout << "它们是互质的。" << endl;
   else
    cout << "它们不是互质的。" << endl;
  
  return 0;
}

这个程序首先使用 `gcd` 函数计算给定两个数的最大公约数，然后使用 `isCoprime` 函数判断它们是否互质。在主函数中，它读取两个整数，并输出它们是否互质。

备注

欧几里得算法的时间复杂度是 O(log(min(a,b)))。这个算法是非常快的，并且可以用于处理很大的整数。

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

下一篇: "C++中派生和继承的区别"

评论区

()

相似文章