С какви данни или структури работи алгоритъмът за намиране на най-големия общ делител (GCD)?

Алгоритъмът за намиране на най-големия общ делител (НОД, GCD) работи с цели числа. Основните данни са две цели числа, за които трябва да се намери максималният делител, който без остатък дели и двете числа.

Обикновено се използва алгоритъмът на Евклид, който последователно заменя двойката числа с (b, a % b), докато остатъкът не стане нула. В крайна сметка остава последният ненулев делител — това е НОД.

Пример на 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) // резултатът ще бъде 6