First I check if number if perfect square, next I check if number fits Legendre's condition for 4 squares 4^a(8b+7) .

I check if number is prime and is prime I check that n%4==1. See https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares

If number is not a prime I check if the numbers it's composed of numbers that match Fermat's theorem.

By Brahmagupta–Fibonacci identity

https://en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity

if all factors(or subfactors) are prime and match condtion n%4==1 I am guaranteed that my number is sum of 2 squares. Otherwise it's sum of 3 squares by Legendre's theorem .

```
public class Solution {
public int numSquares(int n) {
if (Math.pow((int)Math.sqrt(n), 2) == n){
return 1;
}
while (n%4 == 0){
n = n/4;
}
if (n%8 == 7){
return 4;
}
if (n%2 == 0){
n = n/2; //OK to divide by 2. If N/2 has is sum of 2 squares so will be N.
}
if (isMod41PrimeOrSubP(n)){
return 2;
}
return 3;
}
private boolean isMod41PrimeOrSubP(int num) {
if (num%4 != 1){
return false;
}
for (int i=3; i*i<num; i=i+2){
if (num%i == 0) {
if (num%(i*i) == 0){
return isMod41PrimeOrSubP(num/(i*i));
}
return isMod41PrimeOrSubP(i)&&isMod41PrimeOrSubP(num/i);
}
}
return true;
}
}
```