Welche Daten oder Strukturen verwendet der Algorithmus zur Suche nach dem größten gemeinsamen Teiler (GCD)?

Der Algorithmus zur Suche des größten gemeinsamen Teilers (ggT, GCD) arbeitet mit ganzen Zahlen. Die Hauptdaten sind zwei ganze Zahlen, für die der maximale Teiler gefunden werden soll, der beide Zahlen ohne Rest teilt.

Am häufigsten wird der Euklidische Algorithmus verwendet, der paarweise die Zahlen durch (b, a % b) ersetzt, bis der Rest null ist. Am Ende bleibt der letzte nicht null Teiler — das ist der ggT.

Beispiel in Swift:

func gcd(_ a: Int, _ b: Int) -> Int {
    var a = a
    var b = b
    while b != 0 {
        let temp = b
        b = a % b
        a = temp
    }
    return a
}

let result = gcd(48, 18) // Ergebnis ist 6