如何判断两个数是否互质
如何判断两个数是否互质定理:gcd(a,b) = gcd(b,a mod b)// a和b的最大公因数,a和b的大小没影响。①0和任意自然数的最大公约数就是那个自然数。(0可以除以任何数,自然数可以整除本身,所以最大公约数为那个自然数②互质指最大公约数等于1的两个自然数。③1和任意数互质。判断是否互质代码如下:(如果求最大公因数,输出b即可)//递推bool gcd(int a, int b){i
文章共819字 · 阅读需要大约3分钟
一键AI生成摘要,助你高效阅读
问答
·
如何判断两个数是否互质
定理:gcd(a,b) = gcd(b,a mod b) // a和b的最大公因数,a和b的大小没影响。
①0和任意自然数的最大公约数就是那个自然数。(0可以除以任何数,自然数可以整除本身,所以最大公约数为那个自然数
②互质指最大公约数等于1的两个自然数。
③1和任意数互质。
判断是否互质代码如下:(如果求最大公因数,输出b即可)
//递推
bool gcd(int a, int b)
{
if(a==1||b==1) // 两个正整数中,只有其中一个数值为1,两个正整数为互质数
return true;
while(1)
{ // 求出两个正整数的最大公约数
int t = a%b;
if(t == 0)
{
break;
}
else
{
a = b;
b = t;
}
}
if(b>1) return false;// 如果最大公约数大于1,表示两个正整数不互质
else return true; // 如果最大公约数等于1,表示两个正整数互质
}
//递归(返回最大公约数)
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
下面跟上自己的分析:
递推:
①如果两个数其中一个为1,则两个数互质。
②如果两个数正好可以整除,则不互质(b的值没有变化,输出false)
③如果没有整除则进行递推判断
- 如果两个数将来不互质,那么是相差n个最大公约数,那么进行辗转相除最后是可以变成一个数除以最大公约数,将t变为0,b为最大公约数的情况,无论a和b谁大谁小,具体可以带数尝试一遍流程就理解了。
- 两个数将来互质,辗转相除最后可以将b变为1。
递归:
①b为0,a为最大公约数
②b不为0,返回gcd(b,a%b)的最大公约数
如果互质,最后会返回1;不互质返回最大公约数
参考链接:https://blog.csdn.net/HelloZEX/article/details/82667263
更多推荐
已为社区贡献1条内容
所有评论(0)