# Euklidischer Algorithmus



## Guest (6. Nov 2004)

hallo hab da mal dieses Problem

Schreiben Sie ein Programm das die folgende verbale Beschreibung des Euklidschen Algorithmus
implementiert:
•Seien a,b zwei natürliche Zahlen,von denen der größte gemeinsame Teiler(ggT)gesucht wird.
•Seien z1 und z2 zwei natürlichzahlige Hilfsgrößen.
1.Weise den größeren Wert von a und b der Variablen z1 und den kleineren Wert der Variablen z2
zu.
2.Bestimme den Rest der ganzzahligen Division von z1 durch z2.
3.So lange der Rest ungleich Null ist,führe aus:
1.Weise z1 den Wert z2 zu
2.Weise z2 den Wert des Restes zu
3.Bestimme den Rest der ganzzahligen Division von z1 durch z2
andernfalls gehe zu 4.
4.z2 enthält das gesuchte Ergebnis -->Stop

ich weiss wie der normale ggt implementiert wird nämlich so:

```
import dssz.io.stdin;

/**
 * @version <1>
 * @author  <>
 */

public class Euklid {

 public static void main (String[] args) {
    
     // Eingabestrom von der Konsole
     stdin in = new stdin (); 
    
    // Hilfsvariablen
    int z1,z2;
     
    // Einlesen der ersten Zahl
    int a   = in.getPosInt ("Bitte geben sie die erste natürliche Zahl ein:"), 
    
    // Einlesen der zweiten Zahl        
    b    = in.getPosInt ("Bitte geben sie die zweite natürliche Zahl ein:");
    

    //wenn a = 0 oder b = 0 gib Fehler aus
    if ((a==0)||(b==0)) {
        System.out.println("Fehler!");
    }
    else {
      // solange a ungleich b  
      while (a != b)            
		{
            // wenn a > b
		    if (a > b) 
            // setze a auf a-b    
			a = a-b; 
            // sonst
            else
            // setze b auf b-a                
			b = b-a;         
		}  // Schleife endet wenn a=b
	   // gib a aus
	   System.out.println("Der groesste gemeinsame Teiler ist: " + a);  

        
        
    }
    
    
        
  } // main
} // Ggt
```
aber wie funktioniert das nun mit den Hilsvariablen???

_edit deathbyaclown: code tags !!_


----------



## Gast (6. Nov 2004)

```
class Euklid
{
	public static void main(String[] args)
	{
		int a, b, z1, z2, r;
		
		a=36;
		b=162;
		
		
		if (a<b)
		{
			z2 = a ;
			z1 = b;
		} 
		else
		{
			z1 = a;
			z2 = b;
		}
		
		
		r = z1 % z2; 
		 		
		while (r!=0)
		{
			z1 = z2;
			z2 = r;
			r = z1 % z2;
			
		 }
		 
		 System.out.println("Der GGT von "+ a+ " und "+b+" ist "+ z2);	
	}
}
```
alles oki lösung gefunden

_[Edit by Beni: Danke für die Lösung, aber bitte trotzdem Code-tags verwenden  ]_


----------

