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 * MCDE quindi: mcm = (A * B)/MCDNel 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.
Euclide, il MCD e il MCM
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 * MCDE quindi: mcm = (A * B)/MCDNel 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.