Milyen adatokkal vagy szerkezetekkel működik a legnagyobb közös osztó (GCD) kereső algoritmus?

A legnagyobb közös osztó (LKÖ, GCD) algoritmus egész számokkal működik. A fő adatok két egész szám, amelyekhez meg kell találni a legnagyobb osztót, ami mindkettőt osztja maradék nélkül.

Leggyakrabban az Euklidesz algoritmust használják, amely egymás után cseréli le a számokat (b, a % b), amíg a maradék nem lesz nulla. Végül a legutolsó nem nulla osztó marad meg — ez a LKÖ.

Swift példával:

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) // az eredmény 6 lesz