text: Make two numbers equal by multiplying with their prime factors minimum number of times | C # program for the above approach ; Everything divides 0 ; Function to calculate total number of prime factor with their prime factor ; Iterate while the number is even ; Reduce to half ; Iterate up to sqrt ( N ) ; Iterate while N has factors of i ; Removing one factor of i ; Function to count the number of factors ; Find the GCD ; Find multiples left in X and Y ; Find prime factor of multiple left in X and Y ; Initialize ans ; Check if it possible to obtain X or not ; Check if it possible to obtain Y or not ; Return main ans ; Driver Code ; Given Input ; Function Call
code: using System ; using System . Collections . Generic ; class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ) ; } static Dictionary < int , int > PrimeFactor ( int N ) { Dictionary < int , int > primef = new Dictionary < int , int > ( ) ; while ( N % 2 == 0 ) { if ( primef . ContainsKey ( 2 ) ) { primef [ 2 ] ++ ; } else { primef [ 2 ] = 1 ; } N = N / 2 ; } for ( int i = 3 ; i <= Math . Sqrt ( N ) ; i ++ ) { while ( N % i == 0 ) { if ( primef . ContainsKey ( i ) ) { primef [ i ] ++ ; } else { primef [ i ] = 1 ; } N = N / 2 ; } } if ( N > 2 ) { primef [ N ] = 1 ; } return primef ; } static int CountToMakeEqual ( int X , int Y ) { int gcdofXY = gcd ( X , Y ) ; int newX = Y / gcdofXY ; int newY = X / gcdofXY ; Dictionary < int , int > primeX = PrimeFactor ( newX ) ; Dictionary < int , int > primeY = PrimeFactor ( newY ) ; int ans = 0 ; foreach ( KeyValuePair < int , int > keys in primeX ) { if ( X % keys . Key != 0 ) { return - 1 ; } ans += primeX [ keys . Key ] ; } foreach ( KeyValuePair < int , int > keys in primeY ) { if ( Y % keys . Key != 0 ) { return - 1 ; } ans += primeY [ keys . Key ] ; } return ans ; } static void Main ( ) { int X = 36 ; int Y = 48 ; int ans = CountToMakeEqual ( X , Y ) ; Console . Write ( ans ) ; } }