S jakými daty nebo strukturami pracuje algoritmus pro hledání největšího společného dělitele (GCD)?

Algoritmus hledání největšího společného dělitele (NSD, GCD) pracuje s celými čísly. Hlavními daty jsou dvě celá čísla, pro která je třeba najít maximální dělitel, který bez zbytku dělí obě čísla.

Nejčastěji se používá Euklidův algoritmus, který postupně nahrazuje pár čísel (b, a % b), dokud zbytek není nula. Nakonec zůstává poslední nenulový dělitel — to je NSD.

Pří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ýsledek bude 6