求最小公倍数有哪些算法

求两个或多个整数的最小公倍数（Least Common Multiple, LCM）有几种常见的算法。下面是其中几个常用的：

1. **短除法**：
这是最基础的方法，也称为欧几里得算法的变种。对于两个数a和b，首先用较大数除以较小数，然后用余数去除除数，如此反复直到余数为0。此时除数就是两数的最大公约数（Greatest Common Divisor, GCD）。然后用两数的乘积除以最大公约数即得到LCM。

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   int lcm(int a, int b) {
       return (a * b) / gcd(a, b);
   }

2. **扩展欧几里得算法** + **中国剩余定理**（Chinese Remainder Theorem, CRT）：
对于多个数的情况，先计算所有对之间的最大公约数，再利用扩展欧几里得算法找到每个数关于其他数的倍数关系。然后利用中国剩余定理计算LCM。

3. **质因数分解法**：
分别将每一个数分解成质因数的乘积，然后取每个质因子的最大指数相乘即可得到LCM。

4. **循环质因数分解**：
如果数字比较大，可以考虑使用循环质因数分解（如Pollard's rho算法）结合哈希函数加速寻找质因数的过程。

5. **辗转相除法** 和 **递推公式**：
利用数学公式 `lcm(a, b) = |a * b| / gcd(a, b)`，结合上述的gcd计算方法。

每种方法的选择取决于具体的应用场景，比如效率要求、数据范围等。如果你需要针对特定情况优化，可能还需要根据实际条件进行调整。如果需要处理大量数的情况，算法性能就显得尤为重要。