Ar kādiem datiem vai struktūrām darbojas lielākā kopīgā dalītāja (GCD) meklēšanas algoritms?

Vislielākais kopīgais dalītājs (VKD, GCD) algoritms darbojas ar veselajiem skaitļiem. Galvenie dati ir divi veseli skaitļi, kuriem jāatrod maksimālais dalītājs, kas bez atlikuma dala abus skaitļus.

Visbiežāk tiek izmantots Eiklida algoritms, kas secīgi aizvieto skaitļu pāri ar (b, a % b), līdz atlikums kļūst nulle. Galu galā paliek pēdējais nenulles dalītājs — tas ir VKD.

Piemērs Swift valodā:

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
}

rezultāts = gcd(48, 18) // rezultāts būs 6