Is this sieve really O(n)?

Question

Can anyone please tell me how this is working in 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] ;
        }
    }
}

I think the outer loop will run O(n) time and inner loop will run O(number of primes less than N) in case of prime numbers and O(1) in case of composite. But overall is should be O(n) * O(number of primes less than n). Am i missing something?

Thanks in advance.

Answer 1

The key idea is that each integer between 2 and n is encountered exactly once in the SPF calculation, thus the total number of iterations of the innermost loop is O(n).

The innermost loop fills the SPF array which indicates the smallest prime factor, for each integer between 2 and n.

Indeed, to compute the SPF array, each integer k between 2 and n is represented as k = i*prime[j], where prime[j] is a prime number below all prime factors of i (this is ensured by the prime[j] <= SPF[i] condition which would break the loop otherwise). This means that prime[j] is the smallest prime factor of k. But this representation is unique for each k (i.e. the same k won't be encountered once again, as another k = i2 * prime[j2] factorization, because if prime[j2] is not equal to prime[j] then one of them would not be the smallest prime factor of k). Thus each number k between 2 and n appears exactly once as the product i*prime[j], computed in the innermost loop.