[Solved] Write an algorithm to efficiently find all i and j for any given N such that N=i^j

by


Given that i^j=N, you can solve the equation for j by taking the log of both sides:
j log(i) = log(N) or j = log(N) / log(i). So the algorithm becomes

for i=2 to N
{
    j = log(N) / log(i)
    if((Power(i,j)==N)
       print(i,j)
}

Note that due to rounding errors with floating point calculations, you might want to check j-1 and j+1 as well, but even so, this is an O(n) solution.

Also, you need to skip i=1 since log(1) = 0 and that would result in a divide-by-zero error. In other words, N=1 needs to be treated as a special case. Or not allowed, since the solution for N=1 is i=1 and j=any value.

As M Oehm pointed out in the comments, an even better solution is to iterate over j, and compute i with pow(n,1.0/j). That reduces the time complexity to O(logN), since the maximum value for j is log2(N).

1

solved Write an algorithm to efficiently find all i and j for any given N such that N=i^j