running time for print out all primes under N

Question

int main() {
      int i, a[N];
      // initialize the array
      for(i = 2; i < N; i++) a[i] = 1;
      for(i = 2; i < N; i++)
         if(a[i])
              for(int j = i; j*i < N; j++) a[i*j] =0;
       // pirnt the primes less then N
       for(i = 2; i < N; i++)
           if(a[i]) cout << "  " << i;
       cout << endl;
}

It was given in algorithm book i am reading running time of above program is proportional to N+N/2+N/3+N/5+N/7+N/11+...,

Please help me in understanding how author came up with above equation from the program. Thanks! Venkata

Answer 1

The inner loop (inside if(a[i])) is executed for prime is only. I.e., for i equal to 2, 3, 5, 7, 11, ... And for single i, this loop has approximately N/i iterations. Thus, we have N/2 + N/3 + N/5 + N/7 + N/11 + ... iterations overall.

Answer 2

This algorithm is called the Sieve of Eratosthenes. This image explains everything:

(from Wikipedia)

Answer 3

This is the "Sieve of Eratosthenes" method for finding primes. For each prime, the if(a[i]) test succeeds and the inner loop gets executed. Consider how this inner loop terminates at each step (remember, the condition is j*i < N, or equivalently, j < N/i):

• i = 2 -> j = 2, 3, 4, ..., N/2
• i = 3 -> j = 3, 4, 5, ..., N/3
• i = 4 -> not prime
• i = 5 -> j = 5, 6, 7, ..., N/5
• ...

Summing the total number of operations (including initialising the array/extracting the primes) gives the runtime mentioned in the book.

See this question for more, including a discussion of how, in terms of bit operations, this turns into an expansion of O(n(log n)(log log n)) as per the Wikipedia article.