Jakimi danymi lub strukturami operuje algorytm wyszukiwania największego wspólnego dzielnika (NWD)?

Algorytm wyszukiwania największego wspólnego dzielnika (NWD, GCD) operuje na liczbach całkowitych. Główne dane to dwie liczby całkowite, dla których należy znaleźć największy dzielnik, który bez reszty dzieli obie liczby.

Najczęściej używany jest algorytm Euklidesa, który kolejno zamienia parę liczb na (b, a % b), aż reszta stanie się zerem. Ostatecznie pozostaje ostatni niezerowy dzielnik — to jest NWD.

Przykład w 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) // wynik będzie 6