Maximum GCD among all pairs ( i , j ) of first N natural numbers | Python3 program for the above approach ; Function to find maximum gcd of all pairs possible from first n natural numbers ; Stores maximum gcd ; Iterate over all possible pairs ; Update maximum GCD ; Driver Code
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 maxGCD ( n ) : NEW_LINE INDENT maxHcf = - 2391734235435 ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( i + 1 , n + 1 ) : NEW_LINE INDENT maxHcf = max ( maxHcf , __gcd ( i , j ) ) ; NEW_LINE DEDENT DEDENT return maxHcf ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 ; NEW_LINE print ( maxGCD ( n ) ) ; NEW_LINE DEDENT