这个筛子真的是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)。

最里面的循环填充SPF数组，它为2到n之间的每一个整数指示最小的素数因子。

实际上，为了计算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]的形式出现一次，在最里面的循环中计算出来。