Codewars阶乘分解任务decomp函数n≥23时页面无限循环求解

• 数值溢出：JavaScript 中 Number 类型为双精度浮点数，最大安全整数仅为 2^53 - 1（约9e15），23! 的值已经超过这个阈值，计算得到的sum会出现精度丢失，后续取模、除法逻辑全部异常，直接导致死循环。更何况题目要求支持n最大到4000，4000! 有12674位，不可能用普通数值类型存储。
• 算法效率极低：即使不考虑溢出，遍历k到sum的逻辑时间复杂度完全不可行，大n下根本跑不完。

用Legendre公式直接计算每个质数在n!中的指数，完全不需要计算阶乘本身：对于质数p，n!中p的指数等于 ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ...，直到p的k次方大于n时停止累加。

function decomp(n) {
    // 埃氏筛筛选所有<=n的质数
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    const primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push(i);
    }

    const resArr = [];
    for (const p of primes) {
        let count = 0;
        let current = p;
        while (current <= n) {
            count += Math.floor(n / current);
            current *= p;
        }
        // 按要求格式化输出项
        resArr.push(count === 1 ? `${p}` : `${p}^${count}`);
    }
    return resArr.join(' * ');
}

• 先实现埃氏筛得到所有≤n的质数
• 对每个质数用Legendre公式计算对应指数
• 用动态分配字符串拼接结果，拼接时判断是否为第一个元素避免添加多余前缀，最终输出无尾部空格。

• decomp(12) 返回 "2^10 * 3^5 * 5^2 * 7 * 11"，符合要求
• decomp(22) 返回 "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"，符合要求
• decomp(25) 返回 "2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23"，符合要求

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