Algoritmo del massimo comune divisore

L'algoritmo euclideo per calcolare il massimo comune divisore tra due numeri è molto semplice. Ci sono diversi modi per farlo.

Per evitare di usare un linguaggio di programmazione specifico, sviluppo l'implementazione con uno pseudocodice.

I principali metodi per calcolare il MCD sono i seguenti.

Metodo 1 ( divisione )

1. function gcd(a, b)
2. while b ≠ 0
3. x := b;
4. b := a mod b;
5. a := x;
6. return a;

Metodo 2 ( sottrazione )

1. function gcd(a, b)
2. while a ≠ b
3. if a > b
4. a := a − b;
5. else
6. b := b − a;
7. return a;

Metodo 3 ( ricorsivo )

1. function gcd(a, b)
2. if b = 0
3. return a;
4. else
5. return gcd(b, a mod b);