Goal
In this puzzle you will have to calculate the greatest common divisor (GCD) of two numbers (a and b) thanks to Euclid's algorithm, but you will not have to return just the result but also the different calculation steps.
Example:
If you are asked to calculate the GCD of 25 and 3 you must return:
25=3*8+1
3=1*3+0
GCD(25,3)=1
Reminder:
In mathematics, Euclid's algorithm is an algorithm that calculates the GCD of two integers, that is, the largest integer that divides the two integers, leaving a zero remainder. Euclid's algorithm follows a simple method which is defined by the following equality:
GCD(a,b) = GCD(b,r) with r = a%b
Divide b by the remainder of the division of b by a and continue until you get r=0.
Input
Line 1: An integer a and integer b separated by a space
Output
the different stages of calculating Euclid's algorithm
Example
Output
25=3*8+1
3=1*3+0
GCD(25,3)=1
