In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Der Euklidische Algorithmus ist ein klassisches Problem aus der Mathematik: Wir berechnen den grüßten gemeinsamen Teiler (ggT) von zwei ganzen Zahlen.

Warum ist das bekannt? Weil es eine extrem einfache Idee hat, aber in vielen Bereichen wieder auftaucht: Brüche kürzen, Kryptografie-Grundlagen, Zahlentheorie, und als Übung für Iteration und Rekursion.

In diesem Artikel lernst du, was der Algorithmus macht, warum er funktioniert (ohne Beweis-Overkill) und wie du ihn in Java 17+ sauber implementierst: einmal straightforward und einmal als Alternative.

 

Problemstellung

Gegeben sind zwei ganze Zahlen a und b. Gesucht ist ihr ggT, also die größte positive Zahl, die beide ohne Rest teilt.

  • Die Eingaben sind ganze Zahlen (typisch: int oder long).
  • Negative Werte sollen sinnvoll behandelt werden (der ggT ist trotzdem positiv).
  • Falls eine Zahl 0 ist, gilt: ggT(a, 0) = |a|.
  • Falls beide 0 sind, ist der ggT nicht sinnvoll definiert (das sollten wir abfangen).

Mini-Beispiel:

  1. a = 48, b = 18
  2. Der ggT ist 6, weil 48 % 6 == 0 und 18 % 6 == 0.

 

Die Idee dahinter

Kernkonzept: Mathematische Iteration/Rekursion über den Rest.

Die zentrale Beobachtung ist: Der ggT von a und b ist derselbe wie der ggT von b und a % b. Denn alles, was a und b gemeinsam teilt, teilt auch den Rest a % b.

Das wiederholst du, bis der Rest 0 ist. Dann ist der aktuelle Divisor der ggT.

  • Starte mit (a, b)
  • Ersetze durch (b, a % b)
  • Stoppe, wenn b == 0

 

Schritt für Schritt zur Lösung

  1. Normalisiere die Eingaben: arbeite mit abs(a) und abs(b), damit der ggT positiv ist.
  2. Prüfe Sonderfall: Wenn beide 0 sind, wirf eine Exception (sonst bekommst du keinen sinnvollen ggT).
  3. Solange b != 0, berechne den Rest r = a % b.
  4. Schiebe weiter: Setze a = b und b = r.
  5. Wenn die Schleife endet, ist a der ggT (Rückgabewert).

 

Java-Implementierung (Variante A: straightforward)

public class EuclidStraightforward {

  public static int gcdStraightforward(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);

    if (a == 0 && b == 0) {
      throw new IllegalArgumentException("gcd for 0 and 0 is undefined");
    }

    while (b != 0) {
      int remainder = a % b;
      a = b;
      b = remainder;
    }

    return a;
  }

  public static void main(String[] args) {
    System.out.println(gcdStraightforward(48, 18));   // 6
    System.out.println(gcdStraightforward(21, 14));   // 7
    System.out.println(gcdStraightforward(-42, 56));  // 14
    System.out.println(gcdStraightforward(25, 0));    // 25
  }
}

Diese Variante ist bewusst direkt: eine while-Schleife und ein Zwischenschritt remainder. Durch Math.abs bekommst du einen positiven Rückgabewert, auch wenn Eingaben negativ sind. Der Sonderfall (0, 0) wird klar abgefangen, statt stillschweigend 0 zu liefern.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

public class EuclidAlternative {

  public static int gcdRecursive(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);

    if (a == 0 && b == 0) {
      throw new IllegalArgumentException("gcd for 0 and 0 is undefined");
    }

    return gcdRecursiveNormalized(a, b);
  }

  private static int gcdRecursiveNormalized(int a, int b) {
    if (b == 0) {
      return a; // clear base case
    }

    return gcdRecursiveNormalized(b, a % b);
  }

  public static int gcdIterativeSwap(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);

    if (a == 0 && b == 0) {
      throw new IllegalArgumentException("gcd for 0 and 0 is undefined");
    }

    for (; b != 0; ) {
      int remainder = a % b;
      a = b;
      b = remainder;
    }

    return a;
  }

  public static void main(String[] args) {
    System.out.println(gcdRecursive(48, 18));      // 6
    System.out.println(gcdRecursive(21, 14));      // 7
    System.out.println(gcdIterativeSwap(25, 0));   // 25
  }
}

Hier siehst du die Idee als Rekursion: Die Abbruchbedingung ist sehr deutlich if (b == 0) return a;. Das macht das Prinzip gcd(a, b) = gcd(b, a % b) praktisch 1:1 sichtbar. Zusätzlich ist eine zweite iterative Variante enthalten, die das gleiche tut, aber mit einer kompakteren Schleifenform.

 

Beispiel: Eingabe und Ausgabe

  • Eingabe: a=48, b=18 Output: 6
  • Eingabe: a=21, b=14 Output: 7
  • Eingabe: a=-42, b=56 Output: 14

 

Typische Fehler

  • Falsche Abbruchbedingung: Bei Rekursion if (a == 0) statt if (b == 0) kann zu falschen Ergebnissen oder Endlosschleifen führen.
  • Vergessen, negative Werte zu normalisieren: Ohne Math.abs kann der Rückgabewert negativ sein oder das Verhalten wirkt "komisch".
  • Sonderfall (0, 0) ignorieren: Dann lieferst du oft stillschweigend 0, obwohl der ggT nicht definiert ist.
  • Vertauschen der Variablen in der Schleife: Wenn du a und b in falscher Reihenfolge überschreibst, verlierst du den alten Wert und bekommst Mist.
  • Modulo mit 0: Wenn du a % b berechnest, obwohl b == 0, bekommst du eine Exception. Darum immer erst die Bedingung b != 0 sichern.
  • Zu große Datentypen falsch eingeschätzt: Bei sehr grossen Zahlen kann int überlaufen. Dann lieber long verwenden (Prinzip bleibt gleich).

 

Fazit

Du hast gesehen, wie der Euklidische Algorithmus den ggT über wiederholte Restbildung findet. Dabei eignet er sich perfekt, um Iteration und Rekursion sauber zu vergleichen: gleiche Idee, anderer Stil.