Largest number less than or equal to N / 2 which is coprime to N | Python3 implementation of the above approacdh ; Function to calculate gcd of two number ; Function to check if two numbers are coprime or not ; two numbers are coprime if their gcd is 1 ; Function to find largest integer less than or equal to N / 2 and coprime with N ; Check one by one a numbers less than or equal to N / 2 ; Driver code
import math as mt NEW_LINE def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT else : NEW_LINE INDENT return gcd ( b , a % b ) NEW_LINE DEDENT DEDENT def coPrime ( n1 , n2 ) : NEW_LINE INDENT if ( gcd ( n1 , n2 ) == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def largestCoprime ( N ) : NEW_LINE INDENT half = mt . floor ( N / 2 ) NEW_LINE while ( coPrime ( N , half ) == False ) : NEW_LINE INDENT half -= 1 NEW_LINE DEDENT return half NEW_LINE DEDENT n = 50 NEW_LINE print ( largestCoprime ( n ) ) NEW_LINE