// Finds the largest common factor of two integers (the highest common
// factor, or "HCF") using the Euclidean algorithm. The Euclidean
// algorithm calculates the greatest common divisor of two numbers by
// repeatedly subtracting the smallest number from the largest.
//
// Contributed by Derek (2010).
// Minor alterations by Thomas Larsen (2010).

option explicit

print "The Euclidean algorithm calculates the greatest common divisor of two"
print "numbers by repeatedly subtracting the smallest number from the"
print "largest."
print
input "Enter first number: " first
input "Enter second number: " second

largest = max (abs (first), abs (second))
smallest = min (abs (first), abs (second))

repeat
   tmp_largest = largest
   tmp_smallest = smallest

   largest = max (tmp_largest, tmp_smallest)
   smallest = min (tmp_largest, tmp_smallest)

   print "   " + str$ (largest) + " - " + str$ (smallest) + " = " + str$ (largest - smallest) + "."

   largest = largest - smallest
until largest = 0

print "The greatest common divisor is " + str$ (smallest) + "."