## Algorithm/Insights

Instead of repeated divisions as given in previous method, we can apply mathematical formula as described:

Given a number a, we have to find integers x and y, such that:

a = x^y

If we take log on both sides, we get:

log a = log (x^y)

log a = y log x

y = log a / log x

Hence, we have to find an integer x for which RHS gives an integer y.

**Algorithm:**

1: Starting with i = 2, if (log a / log i) is an integer then return true.

2: Else increment i by 1 till i < √a.

3: If no such i is found, return false.

**Why √number?**

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.

Number = 100, iterate for i = 2 to √100 = 10

log 100 / log 2 = 6.643856189774725

log 100 / log 3 = 4.19180654857877

log 100 / log 4 = 3.3219280948873626

log 100 / log 5 = 2.8613531161467867

log 100 / log 6 = 2.570194417876938

log 100 / log 7 = 2.366589324909877

log 100 / log 8 = 2.2146187299249087

log 100 / log 9 = 2.095903274289385

log 100 / log 10 = 2.0

As 2 is an integer, return true.

Lets take another example.

Number = 625, iterate for i = 2 to √625 = 25

log 625 / log 2 = 9.287712379549449

log 625 / log 3 = 5.859894082871707

log 625 / log 4 = 4.643856189774724

log 625 / log 5 = 4.0

As 4 is an integer, return true.