最大公约数
求最大公约数的两种算法
- 更相减损法
两个整数a、b(a>b),它们的最大公约数为a-b的值c和较小的数b的最大公约数。 - 辗转相除法
两个整数a、b(a>b),它们的最大公约数是a取b的模c和较小的数b的最大公约数。
两种方法未必要严格使得第一个参数大于第二个参数(GcdSub里会判断,GcdMod里多翻转一步就会使其翻转)虽然都能得到正确结果,但是GcdMod会消耗更多时间,因此还是不建议随意放置。尽量保证第一个参数大于第二个
辗转相除
int GcdMod(int m,int n){
return n?Gcd(n,m%n):m
}
相更减损
int GcdSub(int m,int n){
if(m == n){
return m;
}
if(m > n){
return GcdSub((m-n),n);
}
else{
return GcdSub((n-m),m);
}
}
优化
//主要是判断奇偶性,如果两个都为偶数就可以将它们都除以2,然后再将最大公约数乘上这个2就行了
int Gcd(int m,int n){
if( m == n){
return m;
}
if(m == 0){
return n;
}
if(n == 0){
return m;
}
if(~m&1){ //m偶
if(n&1){ //n奇
return Gcd(m>>1,n);
}
else{
return Gcd(n>>1,m>>1)<<1;
}
}
if(~n&1){ //n偶,m奇
return Gcd(n>>1,m);
}
if(m>n){
return Gcd((m-n),n);
}
else{
return Gcd((n-m),m);
}
}
原文链接: https://www.cnblogs.com/ziyuemeng/p/12392671.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/332836
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!