11) Algorithme d'Euclide

U n algorithme est une méthode de résolution d'un problème en suivant un ensemble de règles. L'algorithme d'Euclide a été formulé vers 300 av. J.-c. en vue de trouver le plus grand commun diviseur (PGCD) de deux nombres. Les algorithmes sont essentiels pour l'informatique, et la plupart des appareils électroniques s'en servent.
La plus simple variante de |'algorithme d'Euclide utilise le fait que le PGCD de deux nombres est le même que le PGCD du plus petit des deux et la différence entre eux.
Cela permet d'écarter maintes fois le plus grand des deux nombres impliqués, les réduisant jusqu'a ce que l'un d'entre eux devienne nul. Le dernier nombre différent de zéro est alors le PGCD des deux nombres initiaux.
Pour arriver à la réponse, cette méthode impose de nombreuses répétitions. Une méthode plus efficace, l'algorithme standard, remplace le nombre le plus grand par le reste obtenu en divisant le nombre le plus petit jusqu'à ce qu'il n'y ait plus de reste.