make judge on a natural number: if it's equals to pow(x, 2) and x is a natural number too.
bool isPowered2(int n, int low, int hig, int dvd)
{
int mid = (low+hig)/dvd;
int pwr = mid*mid;
if(pwr == n) return true;
else if(low == hig) return false;
if(pwr > n) { // target number is in [low, mid-1]
return isPowered2(n, low, mid-1, dvd);
}
if(pwr < n) { // target number is in [mid+1, hig]
return isPowered2(n, mid+1, hig, 2); // use binary searching here.
}
}
bool isPowered(int n)
{
if(n <= 100) {
if(n <= 25)
if(n == 1 || n == 4 || n == 9 || n == 16 || n == 25) return true;
if(n == 36 || n == 49 || n == 64 || n == 81 || n == 100) return true;
else return false;
}
return isPowered2(n, 1, n-1, 10); // why use 10 here ?
}