这个筛子真的是 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] 出现一次，在最内层循环中计算。

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

Is this sieve really O(n)?

algorithm

math

primes

sieve