C++实现判断两数是否互质 |21xrx.com

C++实现判断两数是否互质

2023-06-30 17:32:58 深夜i 17 0

C++ 判断互质两数

在数学中，两个整数如果它们的最大公约数为1，那么它们就被称为互质。判断两个数是否互质，可以在C++中使用以下几种方法。

方法一：暴力枚举法

暴力枚举法是一种简单而有效的方法。我们可以枚举这两个数的所有可能的因数，然后判断它们是否有公共因数，如果没有，则它们是互质的。这个方法的时间复杂度为O(min(a,b))。

下面是使用暴力枚举法判断两个数是否互质的C++代码：

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
  if(!b)return a;
  return gcd(b,a%b);
}
int main()
{
  int a,b;
  cin>>a>>b;
  if(gcd(a,b)==1)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

方法二：欧几里得算法

欧几里得算法，也称辗转相除法，是求两个数的最大公约数的一种方法。它可以通过递归的方式求解。我们可以使用递归的方式计算两个数的最大公约数，如果最大公约数为1，则这两个数是互质的。

下面是使用欧几里得算法判断两个数是否互质的C++代码：

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
  if(!b)return a;
  return gcd(b,a%b);
}
int main()
{
  int a,b;
  cin>>a>>b;
  if(gcd(a,b)==1)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

方法三：更相减损法

更相减损法是另一种求两个数的最大公约数的方法。我们可以使用更相减损法来判断两个数是否互质。如果两个数符合更相减损法的条件，并且它们的差为1，则它们是互质的。

下面是使用更相减损法判断两个数是否互质的C++代码：

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
  if(a==b)return a;
  if(a>b)return gcd(a-b,b);
  return gcd(a,b-a);
}
int main()
{
  int a,b;
  cin>>a>>b;
  if(gcd(a,b)==1)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

综上所述，我们可以使用暴力枚举法、欧几里得算法和更相减损法来判断两个数是否互质。其中，最常用的是欧几里得算法和更相减损法。在实际应用中，我们可以根据具体的情况选择合适的方法来判断两个数是否互质。

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

下一篇: 如何将C++指针转换为引用

评论区

相似文章