/***************************  GGT.java  ***************************************/

import AlgoTools.IO;

/**  Berechnung des GGT 
 *  
 *   ggt(x,y) =     groesster gemeinsamer Teiler von x und y
 *   
 *                  x                 falls x = y
 *   ggt(x,y) =     ggt(x-y, y)       falls x > y
 *                  ggt(x, y-x)       falls y > x
 *
 *                  denn wegen x=t*f1 und y=t*f2 folgt (x-y) = t*(f1-f2)
 *
 *                  x                 falls y = 0
 *   ggt(x,y) =     ggt(y, x mod y)   sonst 
 * 
 */

public class GGT {

    public static void main (String [] argv) {

        int teiler, a, b, x, y, z;                  // 6 Integer-Variablen

        IO.println("Bitte zwei Zahlen: ");
        a=x=IO.readInt();  b=y=IO.readInt();        // lies 2 Zahlen ein

        teiler = x;                                 // beginne mit einem teiler
        while ((x % teiler != 0) ||                 // solange x nicht aufgeht 
               (y % teiler != 0))                   // oder y nicht aufgeht
            teiler--;                               // probiere Naechstkleineren
        IO.println("GGT = " + teiler);
 
        while (a != b)                              // solange a ungleich b 
            if (a > b) a = a - b;                   // subtrahiere die kleinere
            else       b = b - a;                   // Zahl von der groesseren 
        IO.println("GGT = " + a);                

        while (y != 0) {                            // solange y ungleich 0
            z = x % y;                              // ersetze x durch y 
            x = y;                                  // und y durch x modulo y 
            y = z;
        }
        IO.println("GGT = " + x);
    }
}