Esercizio 5

Dati due numeri interi calcolare il minimo comune multiplo (mcm). Soluzione: Bisogna ricordarci che dati due numeri interi $a$ e $b$, il minimo comune multimpo $m$ è quel numero per cui si ha che $a\cdot k = m =b \cdot c$ con $k$ e $c$ i due numeri interi più piccoli che verificano tale eguaglianza. Ricordiamo inoltre che quando scriviamo $a \cdot k =$ la somma di $a$ $k$ volte. Sfruttando quanto detto una soluzione diviene:

# leggiamo a e b
a=input("primo numero = ")
b=input("secondo numero = ")
ma=a # multiplo di a ma= a*1 k = 1
mb=b # multiplo di a mb= b*1 c = 1
while ma != mb: # fino a che i multipli sono diversi
    if ma < mb : 
       ma = ma + a # incrementiamo k
    else:
       mb = mb + b # incrementiamo c
print "m.c.m. di ",a," e ",b," = ", ma

Il problema poteva essere risolto con un programma più corto (questa soluzione è stata proposta a lezione da uno studente di biologia) con l'algoritmo seguente:

# leggiamo a e b
a=input("primo numero = ")
b=input("secondo numero = ")
m=1 # multiplo di a e m
while m % b !=0 or m % a !=0 : # fino a che i multipli sono diversi
    m=m+1
print "m.c.m. di ",a," e ",b," = ", ma

Qual'è l'algoritmo più veloce? È interessante provare i due algoritmi con a=100 e b=99 e a=10000 b=9999.