Find pair with maximum GCD in an array | Python program to Find pair with maximum GCD in an array ; function to find GCD of pair with max GCD in the array ; Computing highest element ; Array to store the count of divisors i . e . Potential GCDs ; Iterating over every element ; Calculating all the divisors ; Divisor found ; Incrementing count for divisor ; Element / divisor is also a divisor Checking if both divisors are not same ; Checking the highest potential GCD ; If this divisor can divide at least 2 numbers , it is a GCD of at least 1 pair ; Array in which pair with max GCD is to be found ; Size of array
import math NEW_LINE def findMaxGCD ( arr , n ) : NEW_LINE INDENT high = 0 NEW_LINE i = 0 NEW_LINE while i < n : NEW_LINE INDENT high = max ( high , arr [ i ] ) NEW_LINE i = i + 1 NEW_LINE DEDENT divisors = [ 0 ] * ( high + 1 ) NEW_LINE i = 0 NEW_LINE while i < n : NEW_LINE INDENT j = 1 NEW_LINE while j <= math . sqrt ( arr [ i ] ) : NEW_LINE INDENT if ( arr [ i ] % j == 0 ) : NEW_LINE INDENT divisors [ j ] = divisors [ j ] + 1 NEW_LINE if ( j != arr [ i ] / j ) : NEW_LINE INDENT divisors [ arr [ i ] / j ] = divisors [ arr [ i ] / j ] NEW_LINE INDENT + 1 NEW_LINE DEDENT DEDENT DEDENT j = j + 1 NEW_LINE DEDENT i = i + 1 NEW_LINE DEDENT i = high NEW_LINE while i >= 1 : NEW_LINE INDENT if ( divisors [ i ] > 1 ) : NEW_LINE INDENT return i NEW_LINE DEDENT i = i - 1 NEW_LINE DEDENT return 1 NEW_LINE DEDENT arr = [ 1 , 2 , 4 , 8 , 8 , 12 ] NEW_LINE n = len ( arr ) NEW_LINE print findMaxGCD ( arr , n ) NEW_LINE