Power Of Two Integers

Given a positive integer which fits in a 32 bit signed integer, find if it can be expressed as A^P where P > 1 and A > 0. A and P both should be integers.

Input : 4
Output : True  
as 2^2 = 4. 

思路：

从sqrt(A)开始，一个一个试，看能不能成为A

Solution:

Time: O(nlogn)
Space: O(1)

public class Solution {
    public int isPower(int A) {
        if (A == 1) return 1;
        int sqrt = (int) Math.sqrt(A);
        for (int i = sqrt; i >= 2; i --) {
            int n = A;
            while (n > 0) {
                if (n == i) {
                    return 1;
                }
                if (n % i == 0) {
                    n = n / i;
                } else {
                    break;
                }
            }
        }
        return 0;
    }
}