LOGIC: GCD of powers of prime factors should be greater than 1(C++)


#1

int Solution::isPower(int n) {
if (n==1) return true;

// if gcd of powers of prime factors is greater than 1
// then we can represent it as A^p with p=gcd
int gcd=0;
for(int i=2;i*i<=n;i++)
{
    if(n%i==0)
    {
        int cnt=0;
        while(n%i==0)
        {
            cnt++;
            n/=i;
        }
        gcd=__gcd(gcd,cnt);
    }
}
if(n>1)
    return false;
return (gcd>1);

}