// Euclidean.C
// Math 120 Homework 3 solution, problem 3

#include<iostream.h>

// Given i, j, positive integers, find their GCD

int gcd( int i, int j ) {
   int temp ;  // temporary variable
   int k ; // i - dj, for an approriate integer d, to be determined.

   if ( i<j ) {
      temp = i ;
      i = j ;
      j = temp ;
   }
   // Assert: i>=j

   if ( j==0 ) {
      // we are done
      return i ;
   }

   // else we must reduce the problem to smaller i and j
   // which have the same gcd
   k = i - j*(i/j) ; // NOTE: we know that j != 0
   return gcd( j, k ) ;
}

void main() {
   int i, j ;

   // Get and verify input
   cout << "Enter i: " ;
   cin >> i ;
   if ( i<1 ) {
      cout << "Integer must be positive " << endl ;
      return ; 
   }
   cout << "Enter j: " ;
   cin >> j ;
   if ( j<1 ) {
      cout << "Integer must be positive " << endl ;
      return ; 
   }

   cout << "The GCD is " << gcd(i,j) << endl ;

}