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 <= √number.
If no such factor is found, then return false.
We want to find integers x and y (>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 √a * √a = a
Then for any number, x > √a, x^2 will always be greater than a.
x* x > √a * √a = a
As x^2 > a, x^3 > a, x^4 > a ... i.e. any other power of x will also be greater than a.
So the upper limit on value of x is √a.
Lets take one example to understand the algorithm.
Consider the given number as 100.
Number = 100
Initialize factor = 2
On repeated division by 2 we get: 100 -> 50 -> 25
As further division by 2 is not possible and the number(100) is not reduced to 1,
so we increment factor to 3.
factor = 3
As 100 is not divisible by 3 and the number(100) is not reduced to 1,
so increment factor to 4.
factor = 4
On repeated division by 4 we get: 100 -> 25
As further division by 4 is not possible and the number(100) is not reduced to 1,
so increment factor to 5.
factor = 5
On repeated division by 5 we get: 100 -> 20 -> 4
As further division by 5 is not possible and the number(100) is not reduced to 1,
so increment factor to 6.
factor = 6
As 100 is not divisible by 6, increment to 7.
Similarly, as 100 is not divisible by 7, 8 and 9 also,
increment factor to 10.
factor = 10
On repeated division by 10 we get: 100 -> 10 -> 1
As further division by 10 is not possible and the number is reduced to 1, therefore 100 is a power of 10.
Hence, return true.
Please checkout another solution to this problem:
Check if a number can be expressed as x raised to power y | Set 2