Minimum number of squares whose sum equals to a given number N | Set | Python3 program for the above approach ; Function that returns True if N is a perfect square ; Function that returns True check if N is sum of three squares ; Factor out the powers of 4 ; N is NOT of the form 4 ^ a * ( 8 b + 7 ) ; Function that finds the minimum number of square whose sum is N ; If N is perfect square ; If N is sum of 2 perfect squares ; If N is sum of 3 perfect squares ; Otherwise , N is the sum of 4 perfect squares ; Driver code ; Given number ; Function call
from math import sqrt , floor , ceil NEW_LINE def isPerfectSquare ( N ) : NEW_LINE INDENT floorSqrt = floor ( sqrt ( N ) ) NEW_LINE return ( N == floorSqrt * floorSqrt ) NEW_LINE DEDENT def legendreFunction ( N ) : NEW_LINE INDENT while ( N % 4 == 0 ) : NEW_LINE INDENT N //= 4 NEW_LINE DEDENT if ( N % 8 != 7 ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def minSquares ( N ) : NEW_LINE INDENT if ( isPerfectSquare ( N ) ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if i * i < N : NEW_LINE INDENT break NEW_LINE DEDENT if ( isPerfectSquare ( N - i * i ) ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT DEDENT if ( legendreFunction ( N ) ) : NEW_LINE INDENT return 3 NEW_LINE DEDENT return 4 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 123 NEW_LINE print ( minSquares ( N ) ) NEW_LINE DEDENT