Java最小公倍数算法的最佳实践：性能与可读性，两全其美

# 1. Java最小公倍数算法简介

最小公倍数（Least Common Multiple，简称 LCM）是指两个或多个整数的最小公倍数。在 Java 中，最小公倍数算法用于计算一组整数的最小公倍数，在数学和计算机科学中有着广泛的应用。

最小公倍数算法有多种实现方法，其中最常见的是辗转相除法和质因数分解法。辗转相除法通过重复除以两个整数的最大公约数来计算最小公倍数，而质因数分解法通过分解整数为质因数，然后取每个质因数的最大幂次来计算最小公倍数。

# 2. 最小公倍数算法的理论基础

最小公倍数算法的理论基础主要包括辗转相除法和质因数分解法。

### 2.1 辗转相除法

辗转相除法是一种求取两个数最大公约数（GCD）的算法，而最小公倍数（LCM）与最大公约数有着以下关系：

LCM(a, b) = (a * b) / GCD(a, b)

因此，我们可以通过求取两个数的最大公约数，再根据公式计算出最小公倍数。

辗转相除法的算法步骤如下：

1. 令 `a` 为较大的数，`b` 为较小的数。
2. 求余：计算 `a % b`，得到余数 `r`。
3. 如果 `r` 为 0，则 `b` 即为 `a` 和 `b` 的最大公约数。
4. 否则，令 `a = b`，`b = r`，重复步骤 2 和 3。

**代码块：**

public static int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

**逻辑分析：**

该代码实现了辗转相除法求取最大公约数的算法。它不断将较大的数除以较小的数，并取余数。当余数为 0 时，较小的数即为最大公约数。

**参数说明：**

* `a`：第一个数
* `b`：第二个数

### 2.2 质因数分解法

质因数分解法是一种将一个数分解为其质因数的乘积的方法。最小公倍数可以通过求取两个数质因数分解后的公共质因数的乘积得到。

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

1. 将两个数分解为质因数。
2. 求取公共质因数。
3. 将公共质因数的指数相加。
4. 根据指数构造最小公倍数。

**代码块：**

public static int lcm(int a, int b) {
    int[] factorsA = primeFactors(a);
    int[] factorsB = primeFactors(b);

    int[] commonFactors = new int[factorsA.length];
    int commonFactorCount = 0;

    for (int i = 0; i < factorsA.length; i++) {
        for (int j = 0; j < factorsB.length; j++) {
            if (factorsA[i] == factorsB[j]) {
                commonFactors[commonFactorCount++] = factorsA[i];
                break;
            }
        }
    }

    int lcm = 1;
    for (int i = 0; i < commonFactorCount; i++) {
        int exponent = Math.max(factorsA[i], factorsB[i]);
        lcm *= Math.pow(commonFactors[i], exponent);
    }

    return lcm;
}

private static int[] primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();

    for (int i = 2; i <= n / 2; i++) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }

    if (n > 1) {
        factors.add(n);
    }

    return factors.stream().mapToInt(Integer::intValue).toArray();
}

**逻辑分析：**

该代码实现了质因数分解法求取最小公倍数的算法。它首先将两个数分解为质因数，然后求取公共质因数，并根据指数构造最小公倍数。

**参数说明：**

* `a`：第一个数
* `b`：第二个数

**Mermaid 流程图：**

graph LR
subgraph 辗转相除法
    a[a] --> b[b]
    b --> r[r]
    r --> a
    a --> b
    b --> r
    r --> a
    a --> b
    b --> r
    r --> a
end
subgraph 质因数分解法
    a[a] --> factorsA[factorsA]
    b[