Section 11.2 Algorithme
Dans ce qui suit, on note \(\text{a}\,\%\,\text{b}\) le reste de la division euclidienne de \(\text{a}\) par \(\text{b}\text{.}\)
Algorithme 11.2.1. Algorithme d'Euclide.
-
Entrées :
Assigner à \(\text{a}\) et \(\text{b}\) les deux entiers positifs dont on veut calculer le PGCD.
S'assurer qu'on a \(\text{a}\geq\text{b}\) si on ne veut pas faire une itération inutile.
-
Instructions :
-
Tant que \(\text{a}\,\%\,\text{b}\ne 0\text{,}\)
assigner simulanément à \(\text{a}\) et \(\text{b}\) les valeurs de \(\text{b}\) et de \(\text{a}\,\%\,\text{b}\) dans cet ordre.
-
Sortie : Afficher \(\text{b}\text{.}\)
Voici une implémentation de cet algorithme qui permet de traiter l'exemple 11.1.31.