Sum of Square Numbers

这个就直接两个循环就可以了. 答案有一个是用了费马定理的, 解释的很好. 费马定理说的是, 当前且仅当一个数字的其中一个prime factor是4k+3 (n % 4 == 3)这个形势并且这个prime的个数是偶数, 这个数字可以分成两个数字的平方和.

class Solution {
    public boolean judgeSquareSum(int c) {
        for(int i = 2; i * i <= c; i++) {
            int count = 0;
            if(c % i == 0) { // if i is a factor
                while(c % i == 0) { // remove all i from c
                    count ++;
                    c /= i;
                }
                if (i % 4 == 3 && count % 2 != 0) { // if 4k+3 and count is odd
                    return false;
                }
            }
        }
        if(c % 4 == 3) // in this case, c is a prime number
            return false; // return false, since the count of 4k+3 is 1 (odd) in this case
        else
            return true; // return true, since the count of 4k+3 is 0 (even)
    }
}