Make two numbers equal by multiplying with their prime factors minimum number of times | Javascript 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 ; Given Input ; Function Call
function gcd ( a , b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ) ; } function PrimeFactor ( N ) { let primef = new Map ( ) ; while ( N % 2 == 0 ) { if ( primef . has ( 2 ) ) { primef . set ( 2 , primef . get ( 2 ) + 1 ) ; } else { primef . set ( 2 , 1 ) ; } N = parseInt ( N / 2 , 10 ) ; } for ( let i = 3 ; i <= Math . sqrt ( N ) ; i ++ ) { while ( N % i == 0 ) { if ( primef . has ( i ) ) { primef . set ( i , primef . get ( i ) + 1 ) ; } else { primef . set ( i , 1 ) ; } N = parseInt ( N / 2 , 10 ) ; } } if ( N > 2 ) { primef [ N ] = 1 ; } return primef ; } function CountToMakeEqual ( X , Y ) { let gcdofXY = gcd ( X , Y ) ; let newX = parseInt ( Y / gcdofXY , 10 ) ; let newY = parseInt ( X / gcdofXY , 10 ) ; let primeX = PrimeFactor ( newX ) ; let primeY = PrimeFactor ( newY ) ; let ans = 0 ; primeX . forEach ( ( values , keys ) => { if ( X % keys != 0 ) { return - 1 ; } ans += primeX . get ( keys ) ; } ) ans += 1 ; primeY . forEach ( ( values , keys ) => { if ( Y % keys != 0 ) { return - 1 ; } ans += primeY . get ( keys ) ; } ) return ans ; } let X = 36 ; let Y = 48 ; let ans = CountToMakeEqual ( X , Y ) ; document . write ( ans ) ;