I am trying to understand how to quickly find the number of two squares that can be added to form a number 'n'. This is my reference.
I have written a function that I believe gives me my proper answers, but I need it to run faster. Pretty much what it does is it goes through possible numbers below Square Root of n, and sees if those to numbers squared equals n. I then add 4 to the sum, since it includes when any number is negative (positive when squared). If you understand Java, here is my code:
static int SquaresR2(int n) { int sum = 0; outer: for(int a=0; ab) break outer; sum+=4; System.out.println(n+" = "+a+"^2 + "+b+"^2"); } } } sum*=2; if(Math.sqrt(n)==(int)Math.sqrt(n)) sum+=4; return sum; }
On Wolfram MathWorld it says that finding the Sum of Squares k=2 relates to factoring n to $n=2^{a_{0}} p_{1}^{2_{a_{1}}} ... p_{r}^{2_{a_{r}}} q_{1}^{b_{1}} ... q_{s}^{b_{s}}$ where the $p_{i}$s are primes of the form 4k+3 and the $q_{i}$s are primes of the form 4k+1. I have (almost) no idea what this means.
It also talks about $B=(b_{1}+1)(b_{2}+1)...(b_{r}+1)$, which I also have no understanding of.
I am thinking it has something to do with factoring n using primes. I am a high school senior taking Calculus 1.
Please help me! Thank you in advance.