for(int i = 2; i < N; i   )
    for(int j = 1; j < N; j = j * i)
        sum  = 1

I got

Can we generalize it further?

CodePudding user response：

Using an algebraic identity about logarithms, logᵢ(N) = log N/log i, so we can take log N out as a factor and the summation is then of 1/log i. Approximating this summation as the integral of 1/log x, we get that asymptotically it is O(N/log N), per Wikipedia. Since we previously took out a factor of log N, multiplying by this gives a final result of O(N).