text: Make two numbers equal by multiplying with their prime factors minimum number of times | C ++ program for the above approach ; 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: #include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_map < int , int > PrimeFactor ( int N ) { unordered_map < int , int > primef ; while ( N % 2 == 0 ) { if ( primef . count ( 2 ) ) { primef [ 2 ] += 1 ; } else { primef [ 2 ] = 1 ; } N /= 2 ; } for ( int i = 3 ; i <= sqrt ( N ) ; i ++ ) { while ( N % i == 0 ) { if ( primef . count ( i ) ) { primef [ i ] += 1 ; } else { primef [ i ] = 1 ; } N /= 2 ; } } if ( N > 2 ) { primef [ N ] = 1 ; } return primef ; } int CountToMakeEqual ( int X , int Y ) { int gcdofXY = __gcd ( X , Y ) ; int newX = Y / gcdofXY ; int newY = X / gcdofXY ; unordered_map < int , int > primeX ; unordered_map < int , int > primeY ; primeX = PrimeFactor ( newX ) ; primeY = PrimeFactor ( newY ) ; int ans = 0 ; for ( auto c : primeX ) { if ( X % c . first != 0 ) { return -1 ; } ans += primeX [ c . first ] ; } for ( auto c : primeY ) { if ( Y % c . first != 0 ) { return -1 ; } ans += primeY [ c . first ] ; } return ans ; } int main ( ) { int X = 36 ; int Y = 48 ; int ans = CountToMakeEqual ( X , Y ) ; cout << ans << endl ; return 0 ; }