Non so come mi sia venuto in mente adesso, l'algoritmo di Euclide per calcolare il massimo comun divisore (MCD) di due numeri.
E' semplice e non occorre scomporre i due numeri, che ricordo era la parte tediosa del lavoro.
Supponiamo che i due numeri di cui si deve calcolare il MCD, siano, ad esempio, 196 e 70.
Bene, si può sostituire al maggiore dei due la loro differenza, senza cambiare il risultato: quindi al posto di (196,70) abbiamo (126,70). E poi continuare fino a che uno dei due non diventi 1, e allora i due numeri originari erano primi tra loro e quindi il MCD era proprio 1, oppure i due numeri diventano identici, e quel valore sarà proprio il MCD.
Nel nostro caso:
(196,70) --> (126,70) --> (56,70) --> (56,14) --> (42,14) --> (28,14) --> (14,14).
E quindi il massimo comun divisore tra i due numeri è proprio 14.
Altro piccolo colpo di "magia" per trovare il minimo comune multiplo (mcm). Se moltiplico i due numeri tra di loro, il loro prodotto avrà come fattori quelli non comuni tra i due numeri presi una sola volta, e quelli comuni presi due volte. In altre parole, se sono partito da A e B, ho:
A * B = mcm * MCD
E quindi: mcm = (A * B)/MCD
Nel nostro caso il mcm di 196 e 70 sarà pari a: 196 * 70 / 14 = 980.
Provare per credere, e il tutto senza scomposizioni in fattori primi e senza inganno!
Che vuol dire? Che devo andare a casa ...
L'immagine è tratta da http://www.megghy.it/calcola_numero/index.htm, sito dedicato ai bimbi.
Condividi e segnala 
