How to check if a given number is of the form x^y?

Question

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? :)

Answer 1

"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.)

Answer 2

One way to solve this would be to factorize n, count the individual factors, and find the greatest common denominator of the counts. If GCD is 1, the answer is "no". Otherwise, the answer is "yes".

Here are some examples:

• 7, prime factor 7 (one time). We have one factor repeated once. Answer "no", because the GCD is 1.
• 8, prime factors 2 (3 times). We have one factor with the count of three. Answer "yes", because GCD is 3.
• 144, prime factors 2 (4 times) 3 (2 times). GCD of 4 and 2 is 2, so the answer is "yes".
• 72, prime factors 2 (3 times) 3 (2 times). GCD of 3 and 2 is 1, so the answer is "no".