Минимальное количество чисел, Сумма квадратов которых дает число N Опции

[Tauka]

Есть число N (N<=5000000)
Нужно определить минимальное количество чисел, сумма квадратов каких дает число N. Например, число 61 можна представить в виде суммы квадратов двух чисел 6^2+5^2
Спасибо за внимание. :о)

[Михаил Густокашин]

решение Virt'а неправильное. например, 12 оно разложит на 3^2+1^2+1^2+1^2, т.е. ответ 4, а можно сделать 2^2+2^2+2^2, т.е. получить ответ 3.
однако, более правильное решение имеет сложность порядка N^(3/2), а для ваших ограничений это многовато (хотя, если памяти хватает, то вполне приемлимо).