Calcolare il minimo comune multiplo, mcm, tra due numeri interi a e b.
Il numero più piccolo divisibile sia per a che per b.
Algoritmo 1
Il primo candidato è max(a, b).
Incrementa finché non diventa multiplo di a e b.
a = 6, b = 9
mcm 6 9
9 NO Sì
10 NO NO
.. .. ..
17 NO NO
18 Sì Sì STOP
a = 7, b = 8
mcm 7 8
8 NO Sì
9 NO NO
.. .. ..
55 NO NO
56 Sì Sì STOP
a = 6, b = 18
mcm 6 18
18 Sì Sì STOP
Algoritmo 2
Il primo multiplo di a divisibile per b.
a = 6, b = 9
ma 9
6 NO
12 NO
18 Sì STOP
a = 7, b = 8
ma 8
7 NO
14 NO
.. NO
49 NO
56 Sì STOP
a = 6, b = 18
ma 18
6 NO
12 NO
18 Sì STOP
Algoritmo 3
Il primo multiplo di b divisibile per a.
a = 6, b = 9
mb 6
9 NO
18 Sì STOP
a = 7, b = 8
mb 7
8 NO
16 NO
.. NO
48 NO
56 Sì STOP
a = 6, b = 18
mb 6
18 Sì STOP
Algoritmo 4
Il primo multiplo sia di a che di b
a = 6, b = 9
ma mb ==
6 9 NO
12 9 NO
12 18 NO
18 18 Sì STOP
a = 7, b = 8
ma mb ==
7 8 NO
14 8 NO
14 16 NO
21 16 NO
21 24 NO
28 24 NO
28 32 NO
35 32 NO
35 40 NO
42 40 NO
42 48 NO
49 48 NO
49 56 NO
56 56 Sì STOP
a = 6, b = 18
ma mb
6 18 NO
12 18 NO
18 18 Sì STOP
Algoritmo 6
- Fattorizza a.
- Fattorizza b.
- Per ogni fattore presente scegli la versione con l’esponente più alto.
- Il mcm è il prodotto di tutti i fattori.
a = 16, b = 15
a = 2^4
b = 3 * 5
mcm = 2^4 * 3 * 5 = 240
a = 70, b = 15
a = 2 * 5 * 7
b = 3 * 5
MCD = 2 * 3 * 5 * 7 = 210
a = 32, b = 16
a = 2^5
b = 2^4
MCD = 2^5 = 32
Algoritmo 7
Il minimo comune multiplo può essere calcolato facilmente utilizzando il Massimo Comune Divisore
![]()
a = 6, b = 9
mcm(6, 9) = 6*9/3 = 18
a = 7, b = 8
mcm(7, 8) = 7*8/1 = 56
a = 6, b = 18
mcm(6, 18) = 6*18/6 = 18