Gli studenti delle scuole medie imparano a calcolare il massimo comun divisore (M.C.D.) e il minimo comune multiplo (m.c.m.) tra due o più numeri naturali positivi e per calcolarlo usano in genere una regola basata sulla scomposizione in numeri primi.
Più efficiente dal punto di vista computazionale l'algoritmo di Euclide.
Vediamo prima l'algoritmo per il minimo comune multiplo, che come dice il nome è il più piccolo numero che sia contemporaneamente multiplo dei due (o più) numeri dati in ingresso. E cominciamo dal caso del m.c.m. tra due numeri a e b.
| mult_a | 6 | 12 | 18 | 24 | 30 |
| mult_b | 15 | 15 | 15 | 30 | 30 |
| mult_a < mult_b? | V | V | F | V | F |
| mult_a > mult_b? | F | F | V | F | F |
| mult_a = mult_b? | F | F | F | F | V |
L'idea è quella di andare per tentativi generando alternativamente i multipli di a e b fino a quando non si trova un multiplo comune; quello sarà ovviamente il m.c.m. tra a e b.
Prendiamo come esempio i due numeri a=6 e b=15: si predispongono due righe una per i multipli d 6, l'altra per i multipli di 15; nella prima riga si somma ripetutamente 6, nella seconda 15; ogni volta che in una riga si è raggiunto un numero superiore a quello dell'altra riga si passa a quest'ultima; quando i due numeri sono uguali, in questo caso 30, quello è sicuramente il minimo comune multiplo. Minimo perchè è il primo, comune multiplo perchè le due righe sono proprio quelle dei multipli dei due numeri.
L'algoritmo si realizza facilmente in un qualsiasi linguaggio di programmazione; ecco una versione in un linguaggio tipo C, la tabella sopra ne è la tavola di traccia:
function mcm(a, b){
mult_a = a;
mult_b = b;
while (mult_a != mult_b) { // continua finchè non trova due multipli uguali
while (mult_a < mult_b) mult_a += a; // genera i multipli di a finchè non superano quelli di b
while (mult_b < mult_a) mult_b += b; // genera i multipli di b finchè non superano quelli di a
}
return mult_a;
}
Il caso del m.c.m. tra molti numeri è un po' più complicato: a ogni passo si dovrà trovare il minimo tra gli n multipli e confrontarlo con il multiplo corrente; se questo non è più il minimo si passa al numero successivo. Quando tutti i numeri sono uguali, quello è il m.c.m.
Vediamo ora l'algoritmo per il massimo comun divisore, che come dice il nome è il numero più grande che divida i due (o più) numeri dati in ingresso. E cominciamo dal caso del M.C.D. tra due numeri a e b.
| a | 6 | 6 | 6 | 3 |
| b | 15 | 9 | 3 | 3 |
| a < b? | V | V | F | F |
| a > b? | F | F | V | F |
| a = b? | F | F | F | V |
L'idea è quella di andare per tentativi generando alternativamente i multipli di a e b fino a quando non si trova un multiplo comune; quello sarà ovviamente il m.c.m. tra a e b.
Prendiamo di nuovo come esempio a=6 e b=15: si predispongono due righe, si parte da zero e nella prima riga si somma ripetutamente 6, nella seconda 15; ogni volta che in una riga si è raggiunto un numero superiore a quello dell'altra riga si passa a quest'ultima; quando i due numeri sono uguali, in questo caso 30, quello è sicuramente il minimo comune multiplo. Minimo perchè è il primo, comune multiplo perchè le due righe sono proprio quelle dei multipli dei due numeri.
Anche questo algoritmo si realizza facilmente in un qualsiasi linguaggio di programmazione; ecco una versione in un linguaggio tipo C, la tabella sopra ne è la tavola di traccia:
function MCD(a, b){
while (a != b) { // continua finchè non trova due numeri uguali
while (a < b) b -= a; // sottrae a da b finchè b non diventa minore di a
while (b < a) a -= b; // sottrae b da a finchè a non diventa minore di b
}
return a;
}