C#求解可被1~n整除最小数的函数性能优化咨询

你要实现的功能本质是求1到n所有整数的最小公倍数（LCM）。原代码采用暴力枚举逐次验证的逻辑，存在两个核心问题：

• 时间复杂度极高：当n≥19时，最小公倍数已经达到2329089562800，逐一枚举验证的次数达到千亿级别，耗时自然指数级上升
• 溢出风险：int类型最大值仅为2147483647，n≥13时结果就已经超出int范围，就算跑出来结果也是错误的

我们可以通过最小公倍数的数学性质直接计算结果，完全不需要枚举：

方案1：素因子最高次幂累乘 #

对每个小于等于n的素数p，取满足p^k ≤n的最大指数k，将所有p^k相乘就是最终结果。
比如n=4时：

• 素数2的最高次幂是2²=4
• 素数3的最高次幂是3¹=3
• 乘积4*3=12，和示例结果一致

方案2：递推计算最小公倍数 #

两个数的最小公倍数公式为：LCM(a,b) = a * b / GCD(a,b)，其中GCD是两个数的最大公约数，可以通过欧几里得算法快速计算。
我们可以从1开始递推，逐步计算到n的最小公倍数即可，逻辑实现更简单。

using System.Numerics;

public static string Smallest(int n)
{
    BigInteger result = 1;
    for (int i = 2; i <= n; i++)
    {
        result = Lcm(result, i);
    }
    return result.ToString();
}

// 计算两个数的最大公约数
private static BigInteger Gcd(BigInteger a, BigInteger b)
{
    while (b != 0)
    {
        BigInteger temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算两个数的最小公倍数
private static BigInteger Lcm(BigInteger a, BigInteger b)
{
    return a * b / Gcd(a, b);
}

优化后的代码时间复杂度为O(n log n)，哪怕n到1000也可以在毫秒级返回结果，完全不存在n≥19时耗时过高的问题，且使用BigInteger类型存储结果不会出现溢出错误。

内容的提问来源于stack exchange，提问作者Shahar