Thanks in advance

1) If N==a^2, that is if N is a full square, the answer is 1

2) Try N = a^2 + b^2. Brute force, but "clever" brute force.
This is the most expensive part of the algo

3) N is NOT a sum of 3 squares <=> N=(8k+7)*4^m
This is a fast step, about O(log(N))

4) Lagrange theorem states: each number may be presented as a sum of 4 squares: N = a^2 + b^2 + c^2 + d^2
So if the upper three cases fails, the answer will be 4.

Nice algorithm! Thank you, melkiy.
But you can find N = a^2 + b^2 without brute-force. I considered this case by facrotizing N to primes and using Ferma-Euler theorem.

How to apply Ferma-Euler theorem to this problem ?

No brute force. Moreover, we don't need to find the sum of squares, we need just answer.

find factorization of N = L*m^2, where L is not divisible by p^2 for p is prime.
if L==1 then answer = 1
if L has no prime divisors of the form 4*t+3 then answer = 2 (Fermat)
if N != (8*t+7)*4^k then answer = 3 (Legendre)
else answer = 4

Thank, every body.
+1

Got AC.

Edited by author 22.01.2013 20:14

If L has prime divisors of the form 4*t+3，the answer may be 2,too.
How to explain this question？

Fermat's theorem says that if N=a^2+b^2, then L hasn't prime divisors of the form 4t+3, and back.

A simpler to calculate approach is just to check if the prime decomposition contains no ODD powers of primes that can be expressed as  4*t+3, in which case the answer is two.