a b 的公约数= b a%b的公约数 a大于b，否则交换
证明：
a=kb+r 即 a/b=k a%b=r
设a b的公约数（任意性）为d
b为d的倍数，a为d的倍数, kb自然也是d的倍数
r=a-kb当然也是d的倍数
d为b和r的约数，即d为b和a%b的约数
由于这里d的任意性，可以推出，任意的a b的公约数，都是b和a%b的公约数
公约数全部相同
用递归表示的话，gcd函数用于求最大公约数
gcd（a,b）=gcd（b，a%b）；
递归的边界情况为，gcd（a，0）
即其中一个为0的时候，公约数为另一个数
0和任意一个整数x的最大公约数为x
int gcd(int a,int b) { if(b==0)return a; else return gcd(b,a%b); }
最小公倍数
设a=kd b=jd d为最大公约数
最小公倍数就是jkd=a*b/d
为了避免a*b结果溢出
应该写成(a/d)*b
原文链接: https://www.cnblogs.com/lxzbky/p/12497914.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/400053
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
