How to check if a given number is of the form x^y?
algorithm, math
Solution
"Taking the log and stuff" is the way to go. Note that N > 1 is never a^b for integer a and b > log_2(N). So you can check floor(N^(1/b))^b = N for each integer b between 2 and log_2(N). You have to do about log(N) many exponentiations, each of which produces a number at most the size of N.
This is far faster than @dasblinkenlight's solution, which requires you to factor N first. (No polynomial-time algorithm---that is, polynomial in the number of bits in N, is known for integer factorisation. However, integer exponentiation with a small exponent can be done in polynomial time.)
Problem
I'm preparing for my interviews and came across this question: Write a program to check if a number n is of x^y form. It is known that n, x and y are integers and that x and y are greater than 2. I thought of taking log and stuff but couldn't certainly figure out how to check if the number is of the form. Could any of you please help? :)