Smallest divisor D of N such that gcd ( D , M ) is greater than 1 | C ++ 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 ; Drivers code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinimum ( int n , int m ) { int mini = m ; for ( int i = 1 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) { int 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 ; } int main ( ) { int n = 8 , m = 10 ; cout << findMinimum ( n , m ) ; return 0 ; }