Solution using prime factorization and gcd


#1

int Solution::isPower(int A) {
if(A==1)
return 1;
map<int,int> mp;
int i=2;
while(A!=1)
{
while(A%i==0)
{
mp[i]++;
A/=i;
}
i++;
}
if((int)mp.size()==1 && mp.begin()->second>1)
return 1;
int gcd = 0;
for(auto it: mp)
gcd = __gcd(gcd,it.second);
return gcd>=2;
}


#2

what is the reason to calculate gcd how 1024000000 be expressed as a^p ?? it is 2^16*5^6 then why return true for this case ??can u plzz explain


#3

1024000000=2^16x5^6=(2^8x5^3)x(2^8x5^3)=(2^8x5^3)^2 which is (32000)^2