如何判断两个数是否互质 |
您所在的位置：网站首页 › A和B互为质数什么意思 › 如何判断两个数是否互质 |
|
如何判断两个数是否互质 定理：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 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |