Help me please with some ideas to find number of integer solutions.
$x^2 + y^2 + z^2 = N$
Time limit - $1$ second, $N \leq 10^9$.
My wrong algorithm:
1) Calculate prime numbers on $(0,\sqrt{N})$
2) Compute $\sqrt{N}$ numbers $A_i = N-z^2, z = \sqrt{N}$.
3) For all $A_i$ 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 $\approx 1.7$ seconds but it is bad.