Akými údajmi alebo štruktúrami operuje algoritmus na vyhľadávanie najväčšieho spoločného deliteľa (GCD)?

Algoritmus na vyhľadávanie najväčšieho spoločného deliteľa (NSD, GCD) pracuje s celými číslami. Hlavné údaje sú dve celé čísla, pre ktoré je potrebné nájsť maximálny deliteľ, ktorý delí obe čísla bez zvyšku.

Najčastejšie sa používa Euklidov algoritmus, ktorý postupne nahrádza pár čísel (b, a % b), kým zvyšok nebude nula. Nakoniec zostáva posledný nenulový deliteľ — to je NSD.

Príklad v 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) // výsledok bude 6