Алгоритми ҷустуҷӯи бузургтарин тақсимкунандаи умумӣ (GCD) бо кадом маълумот ё сохторҳо кор мекунад?

Алгоритми барои ёфтани бузургтарин тақсимкунандаи умумӣ (БТУ, GCD) бо рақамҳои пурра кор мекунад. Маълумоти асосӣ ду рақами пурра мебошанд, ки барои онҳо бояд бузургтарин тақсимкунандаи умумӣ ёфт шавад, ки ҳарду рақамро бидуни боқимонда тақсим мекунад.

Беҳтарин усул истифодаи алгоритми Евклид аст, ки пайваста ҷуфтҳои рақамҳоро бо (b, a % b) иваз мекунад, то ки боқимонда нол шавад. Дар охир, охирин тақсимкунандаи нолнашударо мемонад — ин GCD мебошад.

Масалан дар 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
}

ҳосил = gcd(48, 18) // натиҷа 6 хоҳад буд