埃拉托斯特尼筛法的Big O表示法是什么？求自实现代码时间复杂度

先看你提供的代码实现：

function sieve(n)
{
    const numberList = [false, false]; // 0和1不是质数，设为false

    for(let i = 2; i <= n; i++) 
        numberList[i] = true;

    for(let i = 2; i <= Math.sqrt(n); i++)
        {
            if(numberList[i] === false)
                continue;
            
            for(let j = i + 1; j <= n; j++)
            {
                if(j % i === 0)
                    numberList[j] = false;
            }
        }

    const results = [];

    // 收集所有标记为true的质数
    for(let i = 2; i <= n; i++)
    {
        if(numberList[i] === true)
            results.push(i);
    }

    return results; 
}

const primeList = sieve(100);
console.log(`From 1 to 100, there are ${primeList.length} prime numbers`, primeList);

你的实现的时间复杂度分析 #

拆解每个部分的时间开销：

• 初始化数组：第一个循环从2遍历到n，共执行n-1次操作，时间复杂度是O(n)。
• 标记非质数的外层循环：从2遍历到√n，执行次数为O(√n)。
• 标记非质数的内层循环：这是核心差异点——你遍历了从i+1到n的所有数，每次通过j % i === 0判断是否为i的倍数。对于每个质数i，内层循环会执行n-i次操作；对于合数i，会直接跳过。总操作数近似为n * π(√n)（π(x)是小于等于x的质数个数，π(x)≈x/lnx），因此这部分时间复杂度为O(n√n / ln n)，比标准埃氏筛慢很多。
• 收集结果：最后遍历数组收集质数，执行n-1次操作，时间复杂度O(n)。

整体来看，你的实现的时间复杂度由内层循环主导，为O(n√n / ln n)。

标准埃氏筛的优化与时间复杂度 #

标准埃氏筛的内层循环不需要遍历所有数再判断取余，而是直接从i*i开始（因为小于i*i的i的倍数已经被更小的质数标记过），每次以i为步长递增，直接标记非质数。修改后的核心循环如下：

for(let i = 2; i <= Math.sqrt(n); i++) {
    if(numberList[i] === false)
        continue;
    // 从i*i开始，步长i标记所有i的倍数
    for(let j = i * i; j <= n; j += i) {
        numberList[j] = false;
    }
}

这种实现的时间复杂度是O(n log log n)——这是埃氏筛的理论最优时间复杂度。原因是对于每个质数p，我们标记n/p个倍数，总操作数是n*(1/2 + 1/3 + 1/5 + 1/7 + ...)，这个质数倒数和的极限是log log n，因此整体复杂度为O(n log log n)。

总结 #

你的实现逻辑正确，但内层循环的写法没有利用埃氏筛的核心优化，导致时间复杂度更高。改用标准的步长标记方式后，能大幅提升效率，达到埃氏筛的理论最优复杂度。

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