Quali dati o strutture utilizza l'algoritmo per trovare il massimo comun divisore (GCD)?

L'algoritmo per trovare il massimo comun divisore (MCD, GCD) opera con numeri interi. I dati principali sono due numeri interi, per i quali bisogna trovare il divisore massimo che divide entrambi i numeri senza resto.

Il più delle volte si utilizza l'algoritmo di Euclide, che sostituisce sequenzialmente la coppia di numeri con (b, a % b), finché il resto non diventa zero. Alla fine, rimane l'ultimo divisore non nullo — che è il MCD.

Esempio in 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) // il risultato sarà 6