Sum of Square Numbers
给一个数字, 问能不能有两个平方数组成. 这个题嘛…费马定理.可以做, 就是是否有偶数个4k+3这种形式的数字在里面. 然后最后还要判断一下, 是否这个数本身就是质数,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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) } } |