/* Greatest common denominator program

   This program contains three different procedures to compute the
   gcd of two positive integers x and y.  The first procedure, Movedown,
   starts at the smaller of x and y, say x, and decrements until it finds the
   gcd. The second procedure is the standard Euclidean algorithm.  The third
   procedure Moveup begins at one and increments looking for a divisor, it then
   checks to see if x divided by that divisor is the gcd. The main body of the
   program needs to be edited when it is determined which procedure to use.
*/

#include <iostream.h>
#include <ctype.h>

void swap(int & a, int & b);
int euclidean(int a, int b);
int movedown(int a, int b);
int moveup(int a, int b);

void swap(int & a, int & b) {
   int temp;

   temp = a;
   a = b;
   b = temp;
}

int movedown(int a, int b) {
   int gcd;
   bool done = false;

   if(a > b)
      swap(a, b);

   gcd = a;

   while((gcd > 1) && (! done)) {
      if( (a % gcd == 0) && (b % gcd == 0) )
         done = true;
      else
         gcd--;
   }

   return gcd;
}

int euclidean(int a, int b) {
   int gcd;
   int remainder;

   if(a > b)
      swap(a, b);

   remainder = a;
   do {
      gcd = remainder;
      remainder = b % a;
      b = a;
      a = remainder;
   } while (remainder != 0);

   return gcd;
}

int moveup(int a, int b) {
   int divider;
   bool done = false;

   if(a > b)
      swap(a, b);

   divider = 1;

   while( (divider <= a) && (! done) ) {
      if( (a % divider == 0) && (b % (a / divider) == 0) )
         done = true;
      else
         divider++;
   }

   return (a / divider);
}

int main() {
   int x;
   int y;
   int gcd;
   char cont = 'N';

   do {
      cout << "Enter two positive integers x and y: ";
      cin >> x >> y;
      cout << "The program is now computing the GCD of ";
      cout << x << " and " << y << " ..." << endl;

      gcd = moveup(x, y);

      cout << "The GCD of " << x << " and " << y << " is " << gcd << " .";
      cout << endl;
      cout << "Would you like to continue? (y/n): ";
      cin >> cont;
   } while (toupper(cont) == 'Y');

   return 0;
}