algorithm - 这个筛子真的是 O(n) 吗？

Question

谁能告诉我这是如何在 O(n) 中工作的。

http://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/

void manipulated_seive(int N)
{
    // 0 and 1 are not prime
    isprime[0] = isprime[1] = false ;

    // Fill rest of the entries
    for (long long int i=2; i<N ; i++)
    {
        // If isPrime[i] == True then i is
        // prime number
        if (isprime[i])
        {
            // put i into prime[] vector
            prime.push_back(i);

            // A prime number is its own smallest
            // prime factor
            SPF[i] = i;
        }

        // Remove all multiples of  i*prime[j] which are
        // not prime by making isPrime[i*prime[j]] = false
        // and put smallest prime factor of i*Prime[j] as prime[j]
        // [ for exp :let  i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ]
        // so smallest prime factor of '10' is '2' that is prime[j] ]
        // this loop run only one time for number which are not prime
        for (long long int j=0;
             j < (int)prime.size() &&
             i*prime[j] < N && prime[j] <= SPF[i];
             j++)
        {
            isprime[i*prime[j]]=false;

            // put smallest prime factor of i*prime[j]
            SPF[i*prime[j]] = prime[j] ;
        }
    }
}

我认为外循环将运行 O(n) 时间，内循环将在素数的情况下运行 O(小于 N 的素数的数量)，在合数的情况下运行 O(1)。但总的来说应该是 O(n) * O(小于 n 的素数)。我错过了什么吗？

提前致谢。

Answer 1

关键思想是在SPF计算中，2到n之间的每个整数恰好遇到一次，因此最内层循环的总迭代次数为O(n)。

对于 2 到 n 之间的每个整数，最内层的循环填充指示最小质因数的 SPF 数组。

实际上，为了计算 SPF 数组，2 到 n 之间的每个整数 k 表示为 k = i*prime[j] , 其中prime[j]是低于 i 的所有素数因子的素数(这是由 prime[j] <= SPF[i] 条件确保的，否则会中断循环)。这意味着 prime[j]是 k 的最小质因数。但是这种表示对于每个 k 都是唯一的(即相同的 k 不会再次遇到，作为另一个 k = i2 * prime[j2] 因式分解，因为如果 prime[j2] 不相等到 prime[j] 那么其中之一将不是 k 的最小质因数)。因此，介于 2 和 n 之间的每个数字 k 恰好出现一次，即乘积 i*prime[j]。 , 在最内层循环中计算。