public int numSquares1(int n){
  while (n % 4 == 0)   n/=4;
  if (n % 8 == 7)   return 4;
  for (int a=0; a * a <= n; a++) {
    int b=(int)Math.sqrt(n - a * a);
    if (a * a + b * b == n) {
      return 1 + (a > 0 ? 1 : 0);
    }
  }
  return 3;
}

public int numSquares1 ( int n ) { while ( n % 4 == 0 ) n /= 4 ; if ( n % 8 == 7 ) return 4 ; for ( int a = 0 ; a * a <= n ; a ++ ) { int b = ( int ) Math . sqrt ( n - a * a ) ; if ( a * a + b * b == n ) { return 1 + ( a > 0 ? 1 : 0 ) ; } } return 3 ; }
a natural number is . . . 1 . a square if and only if each prime factor occurs to an even power in the number ' s prime factorization . 2 . a sum of two squares if and only if each prime factor that ' s 3 modulo 4 occurs to an even power in the number ' s prime factorization . 3 . a sum of three squares if and only if it ' s not of the form 4a ( 8b + 7 ) with integers a and b . 4 . a sum of four squares . period . no condition . you never need more than four .
