递归写法
int gcd(int a,int b){
return (b==0?a:gcd(b,a%b));
}
非递归写法
int gcd(int a,int b){
int c;
while(b){
c=a;
a=b;
b=c%b
}
return a;
}
这个算法的意思也就是一句话,两个数的最大公约数就等于其中一个数和两数之差的最大公约数(取余也就是多减个几次,本质相同)
下面进行一个简单的证明
求 a b 两数的最大公约数
对于任意一个公约数d
假设a>b,小于的话就交换
a/b=k....x,商k,余数x
也就是a=b*k+x
a=md;
b=nd;
x=a-b*k=(m-n)d 也是d的倍数
意思是,a b 的公因数,就是b x的公因数
下面证明b x的公因数也是a b的公因数
对于任意一个b x 的公因数e
b是e的倍数,x是e的倍数
那么k个b再加x也是e的倍数,k*b+x=a也是e的倍数
b x的公因数就是a b 的公因数
即,b x 和 a b的公因数集合相同,当然最大的也相同
下面再给另外一个证法
求 a b 两数的最大公约数
设a b两数的最大公约数为d
假设a>b,小于的话就交换
a/b=k....x,商k,余数x
也就是a=b*k+x
a=md;
b=nd;
x=a-b*k=(m-n)d 也是d的倍数
总结下,a b 的最大公约数,为b x的约数(这里还不是最大)
设b x的最大公约数为e
那么对于b x的公约数中,e大于等于d
b是e的倍数,x是e的倍数
那么k个b再加x也是e的倍数,k*b+x=a也是e的倍数
b x的最大公约数e,是a的约数(也得不到最大)
那么对于a b的公约数中,e小于等于d
好了,e就等于d
原文链接: https://www.cnblogs.com/lxzbky/p/10546851.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/400140
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!