Check if a number can be expressed as x raised to power y

Check if a number can be expressed as x^y (x raised to power y) - GeeksforGeeks
Given a positive integer n, find if it can be expressed as x^y where y > 1 and x > 0. x and y both are integers.

Check if the number is even or odd, initialize X with 2 or 3 based on that, and then increment X by 2. It will directly reduce the calculations to half.
Also, better approach is to find the prime factors of N, and then use them to find all the X such that X^Y=N.

An alternative approach to the problem could be finding the prime factorization of number n,

i.e. say the prime factorization of n= p1^x1*p2^x2*.......*pk^xk ,

then the number could only be expressed as x^y if and only if gcd(x1,x2,....,xk)!=1;

i.e. if the gcd is 1 or number is prime then it can't be expressed as x^y .

Moreover the time complexity of finding prime factorization is O(sqrt(n)) and gcd is log(n).Finding prime factorization could be improved using some sieve like erasthothenes.

int gcd(int a,int b){
if(a<b){
int t=a;a=b;b=t;
}
if(b==0)
return a;
return gcd(b,a%b);
}
int test_if_power(int n){
bool flag=true;
int t=n;
int curr_gcd=INT_MAX;
// if n==1 then it can't be expresses as x^y for y>1
if(n==1)
    flag=false;
if(n%2==0){
int p=0;
while(n%2==0)
{
n=n/2;
p++;
}
// find the power of 2 in the prime factorization of n
if(p==1)
flag=false;
if(curr_gcd==INT_MAX)
curr_gcd=p;
}

for(int i=3;i<=sqrt(n);i+=2){
if(n%i==0){
int p=0;
while(n%i==0){
n/=i;
p++;
}
// if for any prime factor p the power is 1 then n can not be expressed as x^y
if(p==1)
flag=false;
// if i is the first prime factor of p then set the gcd to power of i;
if(curr_gcd==INT_MAX)
curr_gcd=p;
else
curr_gcd=gcd(p,curr_gcd);
//find the gcd of curr_gcd and the power of prime factor i;

}
}
if(n>2){
flag=false;
}
if(!flag){
// return in case flag is false or curr_gc is 1;
return 0;
}
if(curr_gcd!=1)
cout<<t<<" ";
}

One optimization in above solution is to avoid call to pow() by multiplying p with x one by one.

bool isPower(unsigned int n)

{

    // Base case

    if (n <= 1) return true;

    // Try all numbers from 2 to sqrt(n) as base

    for (int x=2; x<=sqrt(n); x++)

    {

        unsigned  p = x;

        // Keep multiplying p with x while is smaller

        // than or equal to x

        while (p <= n)

        {

            p *= x;

            if (p == n)

                return true;

        }

    }

    return false;

}

The idea is simple try all numbers x starting from 2 to square root of n (given number). For every x, try x^y where y starts from 2 and increases one by one until either x^y becomes n or greater than n.

// Returns true if n can be written as x^y

bool isPower(unsigned n)

{

    if (n==1)  return true;

    // Try all numbers from 2 to sqrt(n) as base

    for (int x=2; x<=sqrt(n); x++)

    {

        unsigned y = 2;

        unsigned p = pow(x, y);

        // Keep increasing y while power 'p' is smaller

        // than n.

        while (p<=n && p>0)

        {

            if (p==n)

                return true;

            y++;

            p = pow(x, y);

         }

    }

    return false;

}

Check if a number can be expressed as x raised to power y
Given a positive integer, find if it can be expressed by integers x and y as x^y where
y > 1 and x > 0.

Example:
Consider the number: 125
Since 125 can be written as x^y where x = 5, y = 3, so return true.
Consider the number: 120
As 120 cannot be expressed as x^y for any integers x > 0 and y > 1, so return false.

    public static boolean isPower(int a) {

        int factor = 2;

        while (factor <= Math.sqrt(a)) {

            int number = a;

            while (number % factor == 0) {

                number /= factor;

            }

            if (number == 1) {

                return true;

            } else {

                factor++;

            }

        }

        return false;

    }

http://www.ideserve.co.in/learn/check-if-a-number-can-be-expressed-as-x-raised-to-power-y-set-2
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.

    public static boolean isPowerMath(int a) {

        if (a == 1)

            return true;

        for (int i = 2; i <= Math.sqrt(a); i++) {

            double value = Math.log(a) / Math.log(i);

            if ((value - (int) value) < 0.000000001) {

                return true;

            }

        }

        return false;

    }

Read full article from Check if a number can be expressed as x^y (x raised to power y) - GeeksforGeeks