求最小公倍数

说明：

求最小公倍数可以在求最大公因数的基础上进行，这样就可以极大提高效率,这里需要明白一个点：

a×bgcd(a,b)\frac{a\times b}{gcd(a,b)}

上面公式中gcd指的是求最大公因数，意思就是说a与b的最小公倍数就是a和b相乘再除以他们两的最大公因数。

Java模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * @description: 求最小公倍数
 * 这里的最小公倍数做了比较大优化(时间复杂度大大降低)，是通过最小公因数来求最小公倍数
 * @author 长白崎
 * @date 2023/4/5 21:00
 * @version 1.0
 */
public class LCD {

    public static void main(String[] args) {
        //测试实例
        System.out.println(lcd(3,4));
    }

    /**
     * 求最小公倍数
     * @param a 数字1
     * @param b 数字2
     * @return 返回最小公倍数
     */
    public static int lcm(int a, int b){
        return a/gcd(a,b)*b; //这里先除法再乘法，避免溢出
    }

    /**
     * 计算最大公因数
     * @param a 数字1
     * @param b 数字2
     * @return 返回最大公因数
     */
    public static int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}