import Prog1Tools.IOTools;
public class ggTPrim //Name muss gleich Dateinamen sein!!
{                       // Berechnet den ggT zweier Zahlen ueber
                         // die Primfaktorenzerlegung.  
  public static void main(String[] args)
  {
   long g ,h, d, ggT, gein, hein, Prg, Prh; 
   g =  IOTools.readLong("Einlesen eines langen g >= 2 zum Test:" );
   h =  IOTools.readLong("Einlesen eines langen h >= 2 zum Test:" );
   System.out.println("   ");
   System.out.println("ggT( " + g + " , " + h + " ) soll ermittelt werden.");
   System.out.println ("   ");
   gein = g;
   hein = h;
   Prg=0;
   Prh= 0;
   d = 2;
   ggT = 1;
                             //Initialisierung beendet!!
   while (d <= g & d <= h)   // Warum muessen wir bis g, h gehen?? Vergleiche PRIM.
                             // Der Beweis muesste so aehnlich wie der in der
			     // Vorlesung fuer die Faktorisierung gehen. Nur jetzt ueber
			     // gemeinsamen Primfaktoren von g_0  und h_0 . 
   {
      while ((g % d ==  0) & (h % d == 0)) // Hier wird der naechste 
                                           // Primfaktor rausgekuerzt. 
      { System.out.println( d +  " ist naechster Primfaktor von " +
         g + " und " + h);       
	  g = g/ d;
          h = h/ d; 
          ggT = ggT * d;
       }
   d++;
   }
   System.out.println("Der ggT ist " + ggT);
   Prg= gein % ggT;
   Prh= hein % ggT;
   System.out.println("Zur Probe etwa Prh = " + Prh + "Prg = " + Prg);
   }
 }