Java最小公倍数算法的性能分析：复杂度与算法选择，科学决策

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

最小公倍数（Least Common Multiple，LCM）是指两个或多个整数的最小公倍数。在Java中，计算最小公倍数有两种常用的算法：辗转相除法和更相减损术。

辗转相除法是一种通过不断求取两个整数的余数来计算最小公倍数的算法。更相减损术则是一种通过不断减去两个整数的较小值来计算最小公倍数的算法。这两种算法各有优缺点，在不同的场景下有不同的适用性。

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

### 2.1 辗转相除法

辗转相除法是一种求解最小公倍数的经典算法，其原理是：

1. 找出两个数的最大公约数（GCD）。
2. 最小公倍数等于两个数的乘积除以最大公约数。

**算法流程：**

graph LR
subgraph 辗转相除法
    a[求两个数的最大公约数] --> b[计算最小公倍数]
end

**代码实现：**

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

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

**逻辑分析：**

`gcd()` 函数使用辗转相除法计算最大公约数。它通过不断求余来找到两个数的公约数，直到余数为 0，此时 a 即为最大公约数。

`lcm()` 函数使用最大公约数和两个数的乘积来计算最小公倍数。

### 2.2 更相减损术

更相减损术也是一种求解最小公倍数的算法，其原理是：

1. 找出两个数的差值。
2. 将较大的数减去较小的数。
3. 重复步骤 1 和 2，直到差值为 0。
4. 最后一个非零差值即为最大公约数。
5. 最小公倍数等于两个数的乘积除以最大公约数。

**算法流程：**

graph LR
subgraph 更相减损术
    a[求两个数的差值] --> b[较大的数减去较小的数] --> a
    a[重复步骤 a 和 b] --> c[差值为 0] --> d[最后一个非零差值即为最大公约数] --> e[计算最小公倍数]
end

**代码实现：**

public static int gcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}

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

**逻辑分析：**

`gcd()` 函数使用更相减损术计算最大公约数。它通过不断减去较小的数来找到两个数的公约数，直到两个数相等，此时 a 即为最大公约数。

`lcm()` 函数使用最大公约数和两个数的乘积来计算最小公倍数。

# 3. Java最小公倍数算法实现

### 3.1 基于辗转相除法的实现

基于辗转相除法的最小公倍数算法实现如下：

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