M.C.D.

Calcolare il massimo comun divisore, MCD, tra due numeri interi a e b.
Il numero più grande che divide sia a che b.

Algoritmo 1

Il primo valore candidato è il più piccolo tra a e b.
Finché il valore non divide entrambi i valori ripeti: “decrementa il valore di 1”.

a = 16, b = 15
  
MCD  16  15
 15  NO  Sì
 14  NO  NO
 ..  ..  ..
  2  NO  NO
  1  Sì  Sì  STOP 
a = 70, b = 15
  
MCD  70  15
 15  NO  Sì
 14  NO  NO
 ..  ..  ..
  6  NO  NO
  5  Sì  Sì  STOP
a = 32, b = 16
  
MCD  32  16
 16  Sì  Sì  STOP

Algoritmo 2

Supponi che il MCD sia 1.
Per ogni numero naturale a partire da 2, se divide sia a che b

  • aggiorna i valori di a e b con i quozienti
  • e moltiplica MCD per il valore.
a = 16, b = 15
  
 a   b div  MCD
             1
16  15   2   1
16  15   3   1
..  ..  ..  ..
16  15  15   1
16  15  16  STOP
a = 70, b = 15
   
 a   b div  MCD
             1
70  15   2   1
70  15   3   1
70  15   4   1
70  15   5   5
14   3   5  STOP
a = 32, b = 16
    
 a   b div  MCD
             1
32  16   2   2
16   8   2   4
 8   4   2   8
 4   2   2  16
 2   1   2  STOP

Algoritmo 3

Fattorizza a.
Fattorizza b
Raccogli i fattori comuni.
Per ogni fattore comune considera l’esponente minore.
Il MCD è il prodotto dei fattori.

a = 16, b = 15
  
a = 2^4
b = 3 * 5
MCD = 1
a = 70, b = 15
   
a = 2 * 5 * 7
b = 3 * 5
MCD = 5
a = 32, b = 16
    
a = 2^5
b = 2^4
MCD = 2^4 = 16

Algoritmo 4

Algoritmo di Euclide