Make two numbers equal by multiplying with their prime factors minimum number of times | Python 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
import math NEW_LINE def PrimeFactor ( N ) : NEW_LINE INDENT ANS = dict ( ) NEW_LINE while N % 2 == 0 : NEW_LINE INDENT if 2 in ANS : NEW_LINE INDENT ANS [ 2 ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ANS [ 2 ] = 1 NEW_LINE DEDENT N = N // 2 NEW_LINE DEDENT for i in range ( 3 , int ( math . sqrt ( N ) ) + 1 , 2 ) : NEW_LINE INDENT while N % i == 0 : NEW_LINE INDENT if i in ANS : NEW_LINE INDENT ANS [ i ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ANS [ i ] = 1 NEW_LINE DEDENT N = N // i NEW_LINE DEDENT DEDENT if 2 < N : NEW_LINE INDENT ANS [ N ] = 1 NEW_LINE DEDENT return ANS NEW_LINE DEDENT def CountToMakeEqual ( X , Y ) : NEW_LINE INDENT GCD = math . gcd ( X , Y ) NEW_LINE newY = X // GCD NEW_LINE newX = Y // GCD NEW_LINE primeX = PrimeFactor ( newX ) NEW_LINE primeY = PrimeFactor ( newY ) NEW_LINE ans = 0 NEW_LINE for factor in primeX : NEW_LINE INDENT if X % factor != 0 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT ans += primeX [ factor ] NEW_LINE DEDENT for factor in primeY : NEW_LINE INDENT if Y % factor != 0 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT ans += primeY [ factor ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT X = 36 NEW_LINE Y = 48 NEW_LINE ans = CountToMakeEqual ( X , Y ) NEW_LINE print ( ans ) NEW_LINE DEDENT