Find original numbers from gcd ( ) every pair | Python 3 implementation of the approach ; Utility function to print the contents of an array ; Function to find the required numbers ; Sort array in decreasing order ; Count frequency of each element ; Size of the resultant array ; Store the highest element in the resultant array ; Decrement the frequency of that element ; Compute GCD ; Decrement GCD value by 2 ;  ; Driver code
from math import sqrt , gcd NEW_LINE def printArr ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT def findNumbers ( arr , n ) : NEW_LINE INDENT arr . sort ( reverse = True ) NEW_LINE freq = [ 0 for i in range ( arr [ 0 ] + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ arr [ i ] ] += 1 NEW_LINE DEDENT size = int ( sqrt ( n ) ) NEW_LINE brr = [ 0 for i in range ( len ( arr ) ) ] NEW_LINE l = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( freq [ arr [ i ] ] > 0 ) : NEW_LINE INDENT brr [ l ] = arr [ i ] NEW_LINE freq [ brr [ l ] ] -= 1 NEW_LINE l += 1 NEW_LINE for j in range ( l ) : NEW_LINE INDENT if ( i != j ) : NEW_LINE INDENT x = gcd ( arr [ i ] , brr [ j ] ) NEW_LINE freq [ x ] -= 2 NEW_LINE DEDENT DEDENT DEDENT DEDENT printArr ( brr , size ) NEW_LINE DEDENT / * reverse array * / NEW_LINE if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 5 , 5 , 5 , 7 , 10 , 12 , 2 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE findNumbers ( arr , n ) NEW_LINE DEDENT