如何高效求解不可约分数？JavaScript代码超时问题求助

你的代码本质是计算欧拉函数φ(n)——也就是小于n且与n互质的正整数个数，对应0-1区间分母为n的最简分数。原方法通过遍历1到n-1逐个计算gcd，时间复杂度为O(n log n)，当n很大（比如10^6以上）时必然超时，我们可以用欧拉函数的数学公式来优化，时间复杂度降至O(√n)。

优化思路：欧拉函数公式 #

对于正整数n，若其质因数分解为 n = p₁^k₁ * p₂^k₂ * ... * p_m^k_m，那么：
φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * ... * (1 - 1/p_m)
其中p₁、p₂…p_m是n的所有不同质因数。

优化后的代码 #

function properFractions(n) {
    if (n <= 1) return 0;
    
    let result = n;
    // 遍历找质因子，范围到sqrt(n)即可
    for (let i = 2; i * i <= n; i++) {
        if (n % i === 0) {
            // 应用公式：乘以(1 - 1/i)，等价于减去result/i
            result -= result / i;
            // 清除n中所有i的因子，避免重复计算同一个质因子
            while (n % i === 0) {
                n /= i;
            }
        }
    }
    // 如果剩余n大于1，说明它本身是一个未被处理的质因子
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

代码说明 #

• 特殊情况处理：n≤1时，0-1区间没有符合条件的分数，直接返回0。
• 质因数分解：从2开始遍历到√n，找到能整除当前n的数i（即质因子），应用公式修正结果后，清除n中所有i的因子，确保每个质因子只计算一次。
• 剩余质因子处理：遍历结束后若n仍大于1，说明剩下的n是一个独立质因子，继续应用公式修正结果。

性能对比 #

• 原方法：当n=1e6时，需要循环999999次，每次计算gcd，耗时极长。
• 优化方法：n=1e6时，只需遍历到1000（√1e6），循环次数不到1000次，计算效率提升几个数量级。

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