MCD – Algoritmo di Euclide
Dopo aver eseguito diverse iterazioni dell’algoritmo, si nota che alcune operazioni sono ripetitive e che la procedura per trovare il massimo comune divisore (MCD) può essere ulteriormente ottimizzata.
Quando usiamo la sottrazione, continuiamo a sottrarre il numero più piccolo da quello più grande finché non otteniamo 0 oppure un valore uguale al MCD. Possiamo accelerare questo processo calcolando il resto della divisione (modulo) del numero più grande per quello più piccolo. Con l’operazione di modulo, dividiamo ripetutamente il numero più grande per quello più piccolo e prendiamo il resto finché tale resto non diventa 0. L’ultimo resto non nullo che otteniamo è il MCD.
Pensa all’operazione di modulo come a un modo più efficiente per calcolare il MCD. Invece di sottrarre molte volte il numero più piccolo da quello più grande, usi la divisione per ridurre il numero più grande. In questo modo, entrambi i numeri vengono via via divisi dai loro divisori comuni, arrivando molto più rapidamente al massimo comune divisore.
a, b = int(input()), int(input())
while a > 0 and b > 0: # In case a or b is 0 => the other one is the GCD
a, b = b, a % b # gcd of (a, b) is the same as gcd of (b, a % b)
d = b if a == 0 else a # if a is 0 => b is GCD, if b is 0 => a is GCD
print('gcd:', d)Questo algoritmo è stato citato per la prima volta in un libro di Euclide, scritto nel 300 a.C.
Facciamo qualche simulazione dell’algoritmo:
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ MCD = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ MCD = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ MCD = 1
Input
L’unica riga di input contiene due interi a e b (0 ≤ a, b ≤ ).
Output
Il programma deve stampare il massimo comune divisore di a e b.
Examples
Input | Output |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB