//  Data Structures with Java by John R. Hubbard
//  Copyright McGraw-Hill, 2001
//  Example 4.13 on page 79
//  Recursive Implementation of the Euclidean Algorithm


public class Ex0413
{ public static int gcd(int m, int n)
  { if (m==n) return n;               // basis
    else if (m<n) return gcd(m,n-m);  // recursion
    else return gcd(m-n,n);           // recursion
  }
  public static void main(String[] args)
  { for (int count = 0 ; count < 10 ; count++)
    { int m = (int)(Math.random()*101 + 1) ;
      int n = (int)(Math.random()*101 + 1) ;
      int gcdmn = gcd(m,n);
      System.out.println("gcd(" + m + "," + n + ") = " + gcdmn);
    }
  }
}