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

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

具体代码段如下（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 时，结束查找，即可找到两者的最大公约数；得证。