Le plus grand diviseur commun (GCD)
Étant donnés deux entiers positifs
a et b, l’objectif est de calculer leur plus grand diviseur commun. Le plus grand diviseur commun d’un nombre est le plus grand entier qui divise à la fois a et b sans laisser de reste.Notez que le plus grand diviseur commun d’un nombre et de 0 est ce nombre lui-même.
Entrée
La seule ligne d’entrée contient deux entiers
a et b (0 ≤ a, b ≤ ).Sortie
Le programme doit afficher le plus grand diviseur commun de
a et b.Exemples
Entrée | Sortie |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
Explication
- 8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ le plus grand commun est 4
- 54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ le plus grand commun est 6
- 17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ le plus grand commun est 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB