GCD与LCM

本篇将讲述一下辗转相除法

GCD（欧几里得）算法求的是两数的最大公约数

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

LCM算法则是在GCD的基础上算出两数的最小公倍数

 

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： ⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则 gcd(a,b) = gcd(b,r) ⒉ a 和其倍数之最大公因子为 a。 另一种写法是： ⒈ 令r为a/b所得余数（0≤r<b） 若 r= 0，算法结束；b 即为答案。 ⒉ 互换：置 a←b，b←r，并返回第一步。

代码如下:

GCD给出了上述第二种互换的代码实现：

inline int gcd(int a,int b)
{
    return !b? a:gcd(b,a%b);
 } 
 
inline int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

View Code

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄