Java最小公倍数算法的算法比较：不同算法的优缺点，知己知彼

# 1. Java最小公倍数算法概述**

最小公倍数（Least Common Multiple，简称 LCM）是两个或多个整数的最小公倍数。在 Java 中，有多种算法可以计算最小公倍数，包括辗转相除法、倍数法和质因数分解法。这些算法各有优缺点，适用于不同的场景。

# 2. Java最小公倍数算法理论比较

### 2.1 辗转相除法

#### 2.1.1 算法原理

辗转相除法是一种求最大公约数（GCD）的算法，它基于以下原理：两个数的最大公约数等于其中较小数与两数之差的最大公约数。

辗转相除法的具体步骤如下：

1. 将两个数设为 `a` 和 `b`，其中 `a` 是较大数，`b` 是较小数。
2. 求 `a` 和 `b` 的余数 `r`，即 `a = b * q + r`。
3. 如果 `r` 为 0，则 `b` 是 `a` 和 `b` 的最大公约数。
4. 否则，将 `b` 替换为 `r`，重复步骤 2 和 3。

#### 2.1.2 时间复杂度分析

辗转相除法的平均时间复杂度为 `O(log min(a, b))`，其中 `min(a, b)` 表示 `a` 和 `b` 中的较小值。这是因为在每一步中，较小数都会被除以 2，因此步骤的次数不会超过 `log min(a, b)`。

### 2.2 倍数法

#### 2.2.1 算法原理

倍数法是一种求最小公倍数（LCM）的算法，它基于以下原理：两个数的最小公倍数等于其中较小数的倍数中，第一个同时也是较大数的倍数。

倍数法的具体步骤如下：

1. 将两个数设为 `a` 和 `b`，其中 `a` 是较大数，`b` 是较小数。
2. 求 `a` 的倍数 `m`，即 `m = a * i`，其中 `i` 是一个正整数。
3. 判断 `m` 是否同时是 `b` 的倍数，即 `m % b == 0`。
4. 如果是，则 `m` 是 `a` 和 `b` 的最小公倍数。
5. 否则，`i` 加 1，重复步骤 2 和 3。

#### 2.2.2 时间复杂度分析

倍数法的平均时间复杂度为 `O(min(a, b))`。这是因为在最坏的情况下，`m` 必须遍历 `min(a, b)` 个倍数，才能找到第一个同时也是 `b` 的倍数。

### 2.3 质因数分解法

#### 2.3.1 算法原理

质因数分解法是一种求最小公倍数的算法，它基于以下原理：两个数的最小公倍数等于其质因数分解后所有质因数的乘积，且每个质因数的指数取两数质因数分解中该质因数指数的最大值。

质因数分解法的具体步骤如下：

1. 将两个数设为 `a` 和 `b`。
2. 对 `a` 和 `b` 进行质因数分解，得到质因数分解式 `a = p1^e1 * p2^e2 * ... * pn^en` 和 `b = q1^f1 * q2^f2 * ... * qm^fm`，其中 `p1, p2, ..., pn` 和 `q1, q2, ..., qm` 是质数，`e1, e2, ..., en` 和 `f1, f2, ..., fm` 是对应的指数。
3. 求出两个质因数分解式中所有质因数的集合 `S = {p1, p2, ..., pn, q1, q2, ..., qm}`。
4. 对于集合 `S` 中的每个质因数 `p`，求出其在 `a` 和 `b` 的质因数分解式中的最大指数 `max(e1, f1)`。
5. 将所有质因数 `p` 的最大指数乘积，得到最小公倍数 `LCM = p1^max(e1, f1) * p2^max(e2, f2) * ... * pn^max(en, fn)`。

#### 2.3.2 时间复杂度分析

质因数分解法的平均时间复杂度为 `O(sqrt(min(a, b)))`。这是因为在最坏的情况下，`a` 和 `b` 的质因数分解中可能包含 `sqrt(min(a, b))` 个质因数。

# 3. Java最小公倍数算法实践比较**

### 3.1 算法实现

#### 3.1.1 辗转相除法实现

public static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

**代码逻辑分析：**

* `gcd` 方法采用辗转相除法计算两个数的最大公约数。当 `b` 为 0 时，说明 `a` 为最大公约数，直接返回 `a`。否则，递归调用 `gcd` 方法，用 `b` 除以 `a` 的余数作为新的 `a`，继续计算最大公约数。
* `lcm` 方法利用最大公约数和最小公倍数之间的关系计算最小公倍数。最小公倍数等于两个数的乘积除以最大公约数。

#### 3.1.2 倍数法实现

public static int lcm(int a, int b) {
    int lcm = Math.max(a, b);
    while (true) {
        if (lcm % a == 0 && lcm % b == 0) {
            break;
        }
        lcm++;
    }
    return lcm;
}

**代码逻辑分析：**

* 倍数法从两个数的最大值开始，不断递增，直到找到一个数同时是两个数的倍数。
* `Math.max(a, b)` 函数返回两个数中较大的一个，作为最小公倍数的初始值。
* 循环不断增加 `lcm` 的值，直到找到一个同时满足 `lcm % a == 0` 和 `lcm % b == 0` 的数。
* 由于 `lcm` 始终大于或等于 `a` 和 `b`，因此最终一定会找到一个最小公倍数。

#### 3.1.3 质因数分解法实现

public static int lcm(int a, int b) {
    Map<Integer, Integer> primeFactorsA = pri