algorithme [Al Khwarizmi, mathématicien arabe] :

 

algorithme

Suite finie de règles à appliquer dans un ordre précis en vue d'obtenir un résultat déterminé en un nombre fini d'étapes.

Un programme informatique est un algorithme rédigé dans un langage compris par un ordinateur.
Algorithme des soustractions d'Euclide pour déterminer le pgcd de deux entiers.

 

algorithme des divisions d'Euclide pour déterminer le pgcd de deux entiers est fondé sur le théorème suivant :

Dans la division euclidienne de a par b, a=bq+r :
1) Lorsque le reste est nul, l'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs de b.
2) Lorsque le reste est non nul, l'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs communs à b et r.

Pour déterminer le pgcd de deux entiers a et b, il faut diviser a par b, puis b par r, ... jusqu'à obtention d'un reste nul. Le pgcd est alors le dernier reste non nul.

Soit a=963 et b=153
963=1536+45
153=453+18
45=182+9
18=92+0
le pgcd de 963 et 153 est le dernier reste non nul, c'est à dire 9.

 

algorithme de factorisation