running time for print out all primes under N

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 pro开发者_开发问答portional 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

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.

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

(from Wikipedia)

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.