最大公约数和最小公倍数小结

OO~ posted @ 2014年2月27日 19:30 in C/C++ && 算法 , 1761 阅读

  这个问题每个人都能很好的解决,但是很久没搞算法这一块,都忘了,所以在这里记录,方便以后温故而知新。

  欲求最小公倍数,可以先求出最大公约数。而求解最大公约数的最简方法在数论中称辗转相除法,也叫做欧几里得算法。该算法不需要因式分解。

  具体代码段如下(gcd 为最大公约数,lcm 为最小公倍数):

total = m * n;
while(n) {
    tmp = m % n;
    m = n;
    n = tmp;
}
gcd = m;
lcm = total / gcd;

或者如代码段:

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

  最大公约数可以这么求证明如下:

假设 a % b = t,则 a = kb + t;我们可以知道 t 和 a、b 的最大公约数是一致的,因为 a = m(gcd), b = n(gcd),上述式子进一步可以表示为 m(gcd) = kn(gcd) + t,则 (m - kn)gcd = t。所以求解 a 和 b 的最大公约数之需要求 b 和 t 的最大公约即可,如此下去,最后当 t = 0 时,结束查找,即可找到两者的最大公约数;得证。

 

Avatar_small
hustlijian 说:
2014年3月01日 18:53

http://fayaa.com/code/view/206/


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter