Make two numbers equal by multiplying with their prime factors minimum number of times | Java 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
import java . util . * ; public class Main { static int gcd ( int a , int b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ) ; } static HashMap < Integer , Integer > PrimeFactor ( int N ) { HashMap < Integer , Integer > primef = new HashMap < Integer , Integer > ( ) ; while ( N % 2 == 0 ) { if ( primef . containsKey ( 2 ) ) { primef . put ( 2 , primef . get ( 2 ) + 1 ) ; } else { primef . put ( 2 , 1 ) ; } N = N / 2 ; } for ( int i = 3 ; i <= Math . sqrt ( N ) ; i ++ ) { while ( N % i == 0 ) { if ( primef . containsKey ( i ) ) { primef . put ( i , primef . get ( i ) + 1 ) ; } else { primef . put ( i , 1 ) ; } N = N / 2 ; } } if ( N > 2 ) { primef . put ( N , 1 ) ; } return primef ; } static int CountToMakeEqual ( int X , int Y ) { int gcdofXY = gcd ( X , Y ) ; int newX = Y / gcdofXY ; int newY = X / gcdofXY ; HashMap < Integer , Integer > primeX = PrimeFactor ( newX ) ; HashMap < Integer , Integer > primeY = PrimeFactor ( newY ) ; int ans = 0 ; for ( Map . Entry keys : primeX . entrySet ( ) ) { if ( X % ( int ) keys . getKey ( ) != 0 ) { return - 1 ; } ans += primeX . get ( keys . getKey ( ) ) ; } for ( Map . Entry keys : primeY . entrySet ( ) ) { if ( Y % ( int ) keys . getKey ( ) != 0 ) { return - 1 ; } ans += primeY . get ( keys . getKey ( ) ) ; } return ans ; } public static void main ( String [ ] args ) { int X = 36 ; int Y = 48 ; int ans = CountToMakeEqual ( X , Y ) ; System . out . println ( ans ) ; } }