求最大公约数(gcd)和最小公倍数(lcm)算法

2022-01-05 数学

【求最大公约数(gcd)和最小公倍数(lcm)算法】1.最大公约数：
算法思想是欧几里得的辗转相除法，gcd(a,b)=gcd(b,a%b)。

int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }

2.最小公倍数：
最小公倍数的求法利用了最大公约数，即lcm(a,b)=a/gcd(a,b)*b

int lcm(int a,int b){ return a/gcd(a,b)*b; }

注意：不要写成a*b/gcd(a,b)，看似相等，但是当a和b很大时会发生溢出！！

推荐阅读

上一篇：Android APP开屏界面倒计时圆圈的实现

下一篇：javascript|图片列表（鼠标移入移出改变图片的透明度）