怎么求两个整数的最小公倍数

求两个整数的最小公倍数（Least Common Multiple, LCM），可以使用多种方法。以下是其中一种常见的欧几里得算法（Euclidean Algorithm）结合短除法的思想：

1. **欧几里得算法**：对于整数a和b（假设a>b），如果a能被b整除，那么LCM(a, b)等于b；如果a不能被b整除，那么LCM(a, b)等于LCM(b, a%b)，这里的%表示取模运算。

   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. **短除法**：这是一种直观的方式，将两个数分解质因数，然后相乘得到它们的公倍数。找到每个质因数的最大指数作为最小公倍数中的该质因数的指数。

例如，如果你有整数a = p1^e1 * q1^f1 和 b = p2^e2 * q2^f2，其中p和q是不同的质数，那么LCM(a, b)就是p1的最高次幂、q1的最高次幂、p2的最高次幂以及q2的最高次幂。