Given a positive integer, find if it can be expressed by integers x and y as x^y where y is greater than 1 and x is greater than 0.
Example:
Consider the number: 125
Then 125 can be written as 5x5x5 = 5^3
Here x = 5, y = 3. Hence return true.
Consider the number: 120
As 120 cannot be expressed as x^y for any integers x is greater than 0 and y is greater than 1,
so, we return false.
Algorithm:
1: Initialize factor = 2.
2: Check if number is divisible by ‘factor’. If yes, then keep on dividing the number by factor till it is divisible by factor.
3: After step 2, if we are left with number = 1, then number can be represented as a power of factor, so return true. Else, increment factor by 1.
4: Repeat steps 2 and 3 till factor is less than or equal to squareRoot(number).
5: If no such factor is found, then return false.
Why squareRoot(number)?
We want to find integers x and y (greater than 1) such that x^y = given number ‘a’.
i.e. if for any x, if x^2 = a or x^3 = a or …x^y = a, for some integer y, return true.
Can we have upper limit on value of x from above condition? Let’s find out!
Now, we know that squareRoot(a) * squareRoot(a) = a
Then for any number, x greater than squareRoot(a), x^2 will always be greater than a.
x* x is greater than squareRoot(a) * squareRoot(a) = a
As x^2 is greater than a: x^3 is greater than a, x^4 is greater than a… i.e. any other power of x will also be greater than a.
So the upper limit on value of x is squareRoot(a).
Code and Algorithm Visualization:
[ Ссылка ]
Website: [ Ссылка ]
Facebook: [ Ссылка ]
