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
< ? php function findMaxGCD ( $ arr , $ n ) { $ high = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ high = max ( $ high , $ arr [ $ i ] ) ; $ divisors = array_fill ( 0 , $ high + 1 , 0 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { for ( $ j = 1 ; $ j <= ( int ) ( sqrt ( $ arr [ $ i ] ) ) ; $ j ++ ) { if ( $ arr [ $ i ] % $ j == 0 ) { $ divisors [ $ j ] ++ ; if ( $ j != ( int ) ( $ arr [ $ i ] / $ j ) ) $ divisors [ ( int ) ( $ arr [ $ i ] / $ j ) ] ++ ; } } } for ( $ i = $ high ; $ i >= 1 ; $ i -- ) if ( $ divisors [ $ i ] > 1 ) return $ i ; } $ arr = array ( 1 , 2 , 4 , 8 , 8 , 12 ) ; $ n = sizeof ( $ arr ) ; echo findMaxGCD ( $ arr , $ n ) ; ? >