/*
   Greatest common divisor between a and b

   Write a=qb+r then GCD(a,b) = GCD (b,r) and iterate while r>0
   
   Please enter an int:1260
Please enter an int:198
a=q b+r
1260=6*198+72
198=2*72+54
72=1*54+18
54=3*18+0
GCD =18

*/

#include <iostream>

using namespace std;

int main()
{
   int a,b;
   
   cout << "Please enter an int:";
   cin >> a;

   cout << "Please enter an int:";
   cin >> b;

   if (b==0) cout << "GCD(" << a << "," << b << ")=" << a << endl;   

   cout << "a=q b+r\n";

   int q,r,lastr=b;
   do
     {
        q=a/b;    // Integer division quotient
        r=a%b;    // remainder
        
        cout << a << "=" << q << "*" << b << "+" << r << endl;
   
        a=b;
        b=r;
        if (r>0) lastr=r;
     } while (r>0);

   cout << "GCD =" << lastr << "\n"; 

   return 0;
}