//  Data Structures with Java by John R. Hubbard
//  Copyright McGraw-Hill, 2001
//  Problem 4.18 on page 86
//  Recursive implementation of Euclidean algorithm 
//     using remainder operator

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