Algoritmo del minimo comune multiplo
L'algoritmo per trovare il minimo comune multiplo (mcm) tra due numeri si basa sulla formula euclidea.
Lo pseudocodice per calcolare il m.c.m. tra due numeri è composto da due funzioni
- function gcd(a, b)
- while b ≠ 0
- x := b;
- b := a mod b;
- a := x;
- return a;
- function lcm(a, b)
- c=(a*b)/gcd(a,b)
- return c;
La prima funzione gcd() calcola il massimo comune divisore di due numeri.
La seconda funzione lcm() calcola il minimo comune multiplo.
Nota. Per trovare il minimo comune multiplo tra più numeri, è sufficiente iterare l'algoritmo usando l'm.c.m. dei precedenti numeri come primo fattore e il numero successivo come secondo fattore.
