SumOfSquareNumbersOPT [source code]

public class SumOfSquareNumbersOPT {
static
/******************************************************************************/
public class Solution {
    public boolean judgeSquareSum(int c) {
        for (int i = 2; i * i <= c; i++) {
            if (c % i == 0) {
                int count = 0;
                for (; c % i == 0; count++, c /= i) {}
                if (i % 4 == 3 && count % 2 != 0) return false;
            }
        }
        return c % 4 != 3;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SumOfSquareNumbersOPT.Solution tester = new SumOfSquareNumbersOPT.Solution();
        int[] inputs = {
            5, 4, 3, 0, 2, 
        };
        for (int i : inputs) {
            System.out.println(i + " -> " + tester.judgeSquareSum(i));
        }
    }
}

submission 最优解: 10(99.95);
感觉是个数学上的东西, 有点看不懂;

editorial 解5就是这个东西:

public class Solution {  
    public boolean judgeSquareSum(int c) {  
        for (int i = 2; i * i <= c; i++) {  
            int count = 0;  
            if (c % i == 0) {  
                while (c % i == 0) {  
                    count++;  
                    c /= i;  
                }  
                if (i % 4 == 3 && count % 2 != 0)  
                    return false;  
            }  
        }  
        return c % 4 != 3;  
    }  
}

好像是个什么theorem: (http://wstein.org/edu/124/lectures/lecture21/lecture21/node2.html)

A number $n$ is a sum of two squares if and only if all prime factors of $n$ of the form $4m+3$ have even exponent in the prime factorization of $n$.

这里实际实现的时候还 implicitly 使用了一个结论, 就是所有4m+3形式的, 其实都一定是 prime; 所以只要验证是4m+3形式, 就可以保证是 prime了;

具体的思路就是挨个搜索所有的平方根(上限是 sqrt(c)), 然后看这个平方根是不是一个 divisor/factor, 如果是, 求出其 exponent(这个应该会求的, 这个属于非常 fundamental 的一个操作了). 然后检查是否是4m+3形式;
这里一个疑问可能会认为为什么要先求 exponent 然后再验证4m+3? 其实就算i 不是4m+3, 那么我们最后最好还是要把 i 全部都除完, 这样后面的计算才可以进行: 也就是要先消除所有的 factor, 按照从小到大的顺序; 注意这个除的 header 里面写的是什么: 只要 mod 等于0, 说明还有 i, 那么就继续: 这个是一个yes-condition.
不过好像先验证4m+3也可以? 不对, 还是要把所有逮到都除掉, 这样 c 也在减小, 那么循环的上限其实是一直在减小的;

Problem Description

Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:
Input: 5
Output: True
Explanation: 1 1 + 2 2 = 5
Example 2:
Input: 3
Output: False
Difficulty:Easy
Total Accepted:5K
Total Submissions:15.9K
Contributor: Stomach_ache
Companies
linkedin
Related Topics
math
Similar Questions
Valid Perfect Square