Hmm, ich bin ja kein Experte in Zahlentheorie, aber alles was mir bisher eingefallen ist, um eine Zahl additiv in Quadrate zu zerlegen, braucht entweder eine volle Primfaktorisierung der Zahl, ist ein Brute-Force-Ansatz oder liefert nicht garantiert die minimale Anzahl von Summanden.

Nun ist zwar die Lösung über eine Faktorisierung theoretisch sehr befriedigend, aber irgendwie nicht viel schneller als eine schlaue Brute-Force-Methode -- hat hier irgendwer schon eine perfekte Lösung, die schnell und garantiert minimal ist?