/***************************************************************/
/* Verfasser: Prof. Dr. Gregor Büchel                          */
/* Source   : ggT2.java                                        */
/* Zweck    : Berechnung des ggT zu zwei eingegebenen ganzen   */
/*            Zahlen                                           */
/* Stand    : 24.10.2001                                       */
/***************************************************************/

import java.io.*;

class ggT2
{
 public static void main(String args[]) throws IOException
 {int h, a, b, z, n, r, ggT=-1 , i=0;
  BufferedReader in
             = new BufferedReader(new InputStreamReader(System.in));
  System.out.println("Berechnung des ggT zweier ganzer Zahlen a,b:");
  
  /* Tastatureingabe von a und b       */                     
  System.out.println("Bitte a eingeben");
  a=Integer.valueOf(in.readLine().trim()).intValue();
  System.out.println("Bitte b eingeben");
  b=Integer.valueOf(in.readLine().trim()).intValue();
  
  /* Behandlung des Sonderfalls: a=0 oder b=0      */
  if (a==0) ggT=b;
  if (b==0) ggT=a;

  /* Behandlung des regulären Falles               */
  if (a!=0 && b!=0)
  { /* Der ggT ist als positive Zahl zu berechnen  */
    z=a;
    n=b;
    if (a<0) z=-a;
    if (b<0) n=-b;

    /* Der größte Betrag von a und b ist als Zähler zu nehmen */
    if (z<n)
    {h=z;
     z=n;
     n=h;
    }
    
    /* Berechnung des ggT mit euklid. Algorithmus             */
    do
    {r=z%n;
     z=n;
     n=r;
     i=i+1; 
    } while (r>0);
    ggT=z; 
  }
  /* Ergebnisausgabe                               */
  System.out.println("ggT("+a+" , "+b+")= "+ggT);
  System.out.println("[ "+i+" Rechenschritte]");
 }
}