Check whether a number is Non | Python3 program to check if a given number is Non - Hypotenuse number or not . ; Function to find prime factor and check if it is of the form 4 k + 1 or not ; 2 is a prime number but not of the form 4 k + 1 so , keep Dividing n by 2 until n is divisible by 2 ; n must be odd at this point . So we can skip one element ( Note i = i + 2 ) ; if i divides n check if i is of the form 4 k + 1 or not ; while i divides n divide n by i and update n ; This condition is to handle the case when n is a prime number greater than 2 ; Test function ; Driver code
from math import sqrt NEW_LINE def isNonHypotenuse ( n ) : NEW_LINE INDENT while ( n % 2 == 0 ) : NEW_LINE INDENT n = n // 2 NEW_LINE DEDENT for i in range ( 3 , int ( sqrt ( n ) ) + 1 , 2 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT if ( ( i - 1 ) % 4 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT while ( n % i == 0 ) : NEW_LINE INDENT n = n // i NEW_LINE DEDENT DEDENT DEDENT if ( n > 2 and ( n - 1 ) % 4 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT def test ( n ) : NEW_LINE INDENT print ( " Testing ▁ for " , n , " : " , end = " ▁ " ) NEW_LINE if ( isNonHypotenuse ( n ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 11 NEW_LINE test ( n ) NEW_LINE n = 10 NEW_LINE test ( n ) NEW_LINE DEDENT