Check whether a number can be represented by sum of two squares | Check whether a number can be represented by sum of two squares using Fermat Theorem . ; Count all the prime factors . ; Ifany prime factor of the form ( 4 k + 3 ) ( 4 k + 3 ) occurs an odd number of times . ; If n itself is a x prime number and can be expressed in the form of 4 k + 3 we return false . ; Driver Code
def judgeSquareSum ( n ) : NEW_LINE INDENT i = 2 ; NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT count = 0 ; NEW_LINE if ( n % i == 0 ) : NEW_LINE INDENT while ( n % i == 0 ) : NEW_LINE INDENT count += 1 ; NEW_LINE n = int ( n / i ) ; NEW_LINE DEDENT if ( i % 4 == 3 and count % 2 != 0 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT i += 1 ; NEW_LINE DEDENT return n % 4 != 3 ; NEW_LINE DEDENT n = 17 ; NEW_LINE if ( judgeSquareSum ( n ) ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT