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

Code de l'algorithme :

VARIABLES
  A EST_DU_TYPE NOMBRE
  B EST_DU_TYPE NOMBRE
  R EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  LIRE A
  LIRE B
  AFFICHER "PGCD de "
  AFFICHER A
  AFFICHER " et "
  AFFICHER B
  TANT_QUE (B!=0) FAIRE
    DEBUT_TANT_QUE
    R PREND_LA_VALEUR A%B
    A PREND_LA_VALEUR B
    B PREND_LA_VALEUR R
    AFFICHER "= PGCD de "
    AFFICHER A
    AFFICHER " et "
    AFFICHER B
    FIN_TANT_QUE
  AFFICHER "= "
  AFFICHER A
FIN_ALGORITHME

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

Tester l'algorithme :