Minimize divisions by 2 , 3 , or 5 required to make two given integers equal | Function to calculate GCD of two numbers ; Base Case ; Calculate GCD recursively ; Function to count the minimum number of divisions required to make X and Y equal ; Calculate GCD of X and Y ; Divide X and Y by their GCD ; Stores the number of divisions ; Iterate until X != Y ; Maintain the order X <= Y ; If X is divisible by 2 , then divide X by 2 ; If X is divisible by 3 , then divide X by 3 ; If X is divisible by 5 , then divide X by 5 ; If X is not divisible by 2 , 3 , or 5 , then pr - 1 ; Increment count by 1 ; Print the value of count as the minimum number of operations ; Driver Code
def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def minimumOperations ( X , Y ) : NEW_LINE INDENT GCD = gcd ( X , Y ) NEW_LINE X = X // GCD NEW_LINE Y = Y // GCD NEW_LINE count = 0 NEW_LINE while ( X != Y ) : NEW_LINE INDENT if ( Y > X ) : NEW_LINE INDENT X , Y = Y , X NEW_LINE DEDENT if ( X % 2 == 0 ) : NEW_LINE INDENT X = X // 2 NEW_LINE DEDENT elif ( X % 3 == 0 ) : NEW_LINE INDENT X = X // 3 NEW_LINE DEDENT elif ( X % 5 == 0 ) : NEW_LINE INDENT X = X // 5 NEW_LINE DEDENT else : NEW_LINE INDENT print ( " - 1" ) NEW_LINE return NEW_LINE DEDENT count += 1 NEW_LINE DEDENT print ( count ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT X , Y = 15 , 20 NEW_LINE minimumOperations ( X , Y ) NEW_LINE DEDENT