GCD (PGCD) – Algorithme d’Euclide
Après avoir exécuté plusieurs itérations de l’algorithme, on remarque certaines opérations redondantes. En réalité, il est possible d’optimiser la méthode de recherche du plus grand diviseur commun (GCD ou PGCD).
Avec la soustraction, on soustrait le plus petit nombre du plus grand jusqu’à obtenir 0 ou un nombre égal au PGCD. Pour accélérer ce processus, on peut profiter du reste (modulo) obtenu en divisant le plus grand nombre par le plus petit. À l’aide de l’opération modulo, on divise de façon répétée le plus grand nombre par le plus petit et on récupère le reste jusqu’à ce que ce reste soit 0. Le dernier reste non nul obtenu correspond au GCD (PGCD).
Voyez l’opération modulo comme un moyen plus efficace de calculer le PGCD. Plutôt que de soustraire le plus petit nombre du plus grand nombre à plusieurs reprises, vous utilisez la division pour réduire le plus grand nombre. Ce faisant, vous divisez les deux nombres par leurs diviseurs communs, ce qui permet de converger beaucoup plus rapidement vers leur plus grand diviseur commun.
a, b = int(input()), int(input())
while a > 0 and b > 0: # Au cas où a ou b serait 0 => l’autre est le GCD
a, b = b, a % b # le GCD de (a, b) est le même que le GCD de (b, a % b)
d = b if a == 0 else a # si a est 0 => b est GCD, si b est 0 => a est GCD
print('gcd:', d)Cet algorithme a été mentionné pour la première fois dans un livre d’Euclide, rédigé vers 300 av. J.-C.
Faisons quelques simulations :
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ GCD (PGCD) = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ GCD (PGCD) = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ GCD (PGCD) = 1
Entrée
La seule ligne de l’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
Input | Output |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB