Possible Duplicate:
Number of integer solutions: $x^2 + y^2 + z^2 = N$
Help me please with some ideas to find number of integer solutions.
$$x^2+y^2+z^2=N.$$
Time limit - 1 second. $N <= 10^9$.
My wrong algorithm:
1)calculate prime numbers (0..sqrt(N))
2)compute $\sqrt{N}$ numbers $A_i = N-z^2$, z = 1..sqrt(N)$.
3)for all $A_i$ numbers check that it not include primes $4k+3$ in odd powers.
4)Find answer for each $A_i$ with brute force.
Running time of algorithm ~ 1.7 seconds but it is bad.