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