最大公约数和最小公倍数小结
OO~
posted @ 2014年2月27日 19:30
in C/C++ && 算法
, 2674 阅读
这个问题每个人都能很好的解决，但是很久没搞算法这一块，都忘了，所以在这里记录，方便以后温故而知新。
欲求最小公倍数，可以先求出最大公约数。而求解最大公约数的最简方法在数论中称辗转相除法，也叫做欧几里得算法。该算法不需要因式分解。
具体代码段如下（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 时，结束查找，即可找到两者的最大公约数；得证。
2014年3月01日 18:53
http://fayaa.com/code/view/206/
2023年1月22日 22:09
Finding the greatest common divisor (GCD) and least common multiple (LCM) of two numbers can be a tricky problem. Fortunately, there is an algorithm that can help us solve it more easily. The rolling and dividing method, also known as the cheap real diamond rings Euclidean algorithm, is a simple way to find the GCD and LCM of two numbers. With this algorithm, we do not have to factorize the numbers, making the calculation process much easier. To find the LCM, the GCD must be calculated first. With this method, it is much simpler to work through the problem and get the correct answer.