Sum of Square Numbers
给一个数字, 问能不能有两个平方数组成. 这个题嘛…费马定理.可以做, 就是是否有偶数个4k+3这种形式的数字在里面. 然后最后还要判断一下, 是否这个数本身就是质数,
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 in this case
else
return true; // return true, since the count of 4k+3 is 0 (even)
}
}