// gcd.cpp, Maggie Johnson
// Description: An implementation of Euclid's algorithm for computing gcd.
// Fundamental idea of Euclid's algorithm (one of the oldest known algorithms)
// for finding the greatest common divisor of two integers:
// gcd(a, 0) = a
// gcd(a, b) = gcd(b, a % b)  // % means modulo, that is, the remainder of a/b.
// For example, gcd(6, 4) = 2; gcd(12, 18) = 6.

#include <iostream>
using namespace std;

// A non-recursive version of Euclid's algorithm
int gcd (int a, int b) {
  int temp;
  while (b != 0) {
    temp = a % b;
    a = b;
    b = temp;
  }
  return(a);
}

int main () {
  int x, y;
  cout << "Enter two integers: ";
  if (!(cin >> x >> y)) {
    cout << "Please enter only integers" << endl;
  } else {
    cout << "gcd(" << x << ", " << y << ") = " << gcd(x,y) << endl;
  }
  return(0);
}