Massimo comune divisore (GCD)
Dati due numeri interi positivi
a e b, si richiede di calcolarne il massimo comune divisore. Il massimo comune divisore è il numero che divide sia a sia b ed è il più grande tra quelli possibili.Tieni presente che il massimo comune divisore di un qualsiasi numero e 0 è il numero stesso.
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.Esempi
Ingresso | Uscita |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
Spiegazione
- 8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ il più grande comune è 4
- 54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ il più grande comune è 6
- 17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ il più grande comune è 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB