Smallest divisor D of N such that gcd ( D , M ) is greater than 1 | PHP implementation of the above approach ; Function to find the minimum divisor ; Iterate for all factors of N ; Check for gcd > 1 ; Check for gcd > 1 ; If gcd is m itself ; Driver code
< ? php function __gcd ( $ a , $ b ) { if ( $ b == 0 ) return $ a ; return __gcd ( $ b , $ a % $ b ) ; } function findMinimum ( $ n , $ m ) { $ mini = $ m ; for ( $ i = 1 ; $ i * $ i <= $ n ; $ i ++ ) { if ( $ n % $ i == 0 ) { $ sec = $ n / $ i ; if ( __gcd ( $ m , $ i ) > 1 ) { return $ i ; } else if ( __gcd ( $ sec , $ m ) > 1 ) { $ mini = min ( $ sec , $ mini ) ; } } } if ( $ mini == $ m ) return -1 ; else return $ mini ; } $ n = 8 ; $ m = 10 ; echo ( findMinimum ( $ n , $ m ) ) ;