Find original numbers from gcd ( ) every pair | PHP 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
< ? php function gcd ( $ a , $ b ) { return ( $ a % $ b ) ? gcd ( $ b , $ a % $ b ) : $ b ; } function printArr ( $ arr , $ n ) { for ( $ i = 0 ; $ i < $ n ; $ i ++ ) echo $ arr [ $ i ] , " ▁ " ; } function findNumbers ( $ arr , $ n ) { rsort ( $ arr ) ; $ freq = array_fill ( 0 , $ arr [ 0 ] + 1 , 0 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ freq [ $ arr [ $ i ] ] ++ ; $ size = floor ( sqrt ( $ n ) ) ; $ brr = array_fill ( 0 , $ size , 0 ) ; $ l = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ freq [ $ arr [ $ i ] ] > 0 ) { $ brr [ $ l ] = $ arr [ $ i ] ; $ freq [ $ brr [ $ l ] ] -- ; $ l ++ ; for ( $ j = 0 ; $ j < $ l ; $ j ++ ) { if ( $ i != $ j ) { $ x = gcd ( $ arr [ $ i ] , $ brr [ $ j ] ) ; $ freq [ $ x ] -= 2 ; } } } } printArr ( $ brr , $ size ) ; } $ arr = array ( 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 ) ; $ n = count ( $ arr ) ; findNumbers ( $ arr , $ n ) ; ? >