m.c.m.

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

  1. Fattorizza a.
  2. Fattorizza b.
  3. Per ogni fattore presente scegli la versione con l’esponente più alto.
  4. 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

\displaystyle m.c.m.(a, b) = \frac{a*b}{M.C.D.(a, b)}

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