AlgoBox

Présentation de l'algorithme :

L'algorithme est basé sur les deux résultats suivants :

Si A est un entier alors PGCD(A,0)=A
Si A et B sont deux entiers (avec A>B) et si R est le reste de la division euclidienne de A par B alors PGCD(A,B)=PGCD(B,R)
(c'est pour cela que dans l'algorithme, A prend la valeur de B et B prend la valeur de R : le processus peut ainsi se poursuivre)

On procède par division euclidienne successive jusqu'à obtenir un reste nul.
Exemple :
PGCD(1071,1029)
=PGCD(1029,42) car 1071=1029*1+42
=PGCD(42,21) car 1029=42*24+21
=PGCD(21,0) car 42=21*2+0
=21

Fichier AlgoBox associé : pgcd_euclide.alg (faire un clic-droit et utiliser l'option "enregistrer sous" pour télécharger le fichier)

Code de l'algorithme

1   VARIABLES
2     A EST_DU_TYPE NOMBRE
3     B EST_DU_TYPE NOMBRE
4     R EST_DU_TYPE NOMBRE
5   DEBUT_ALGORITHME
6     LIRE A
7     LIRE B
8     AFFICHER "PGCD de "
9     AFFICHER A
10    AFFICHER " et "
11    AFFICHER B
12    TANT_QUE (B!=0) FAIRE
13      DEBUT_TANT_QUE
14      R PREND_LA_VALEUR A%B
15      A PREND_LA_VALEUR B
16      B PREND_LA_VALEUR R
17      AFFICHER "= PGCD de "
18      AFFICHER A
19      AFFICHER " et "
20      AFFICHER B
21      FIN_TANT_QUE
22    AFFICHER "= "
23    AFFICHER A
24  FIN_ALGORITHME