Calcul du PGCD.


1) Voici un algorithme, dû à Euclide, qui détermine le PGCD de 2 nombres naturels a et b.

  si un des nombres est nul, l'autre est le PGCD
  sinon il faut soustraire le plus petit du plus grand
     et laisser le plus petit inchangé.
  Puis, recommencer ainsi avec la nouvelle paire jusqu'à ce que un des deux
  nombres soit nul. Dans ce cas, l'autre nombre est le PGCD.
    Exemple: si a vaut 32 et b vaut 14, on obtient successivement
	32              14
	32-14=18	14
	14	        4=18-14
	14-4=10	        4
	10-4=6	        4
	6-4=2	        4
	4-2=2	        2
	2	        2-2=0


entier a, b

écrire "Introduisez le 1er nombre: "
lire a
écrire "Introduisez le 2ème nombre: "
lire b
tant que NOT (a*b=0) faire
  si a>b alors a <-- a-b
  sinon b <-- b-a
  fsi
ftant
si a=0 alors écrire "PGCD = ", b
sinon écrire "PGCD = ", a
fsi
VAR a,b:LONGINT;

BEGIN
WRITE('Introduisez le 1er nombre: ');READLN(a);
WRITE('Introduisez le 2ème nombre: ');READLN(b);
WHILE NOT (a*b=0) DO
  BEGIN
  IF a>b THEN a:=a-b
  ELSE b:=b-a;
  END;
IF a=0 THEN WRITELN ('PGCD=',b)
ELSE WRITELN ('PGCD=',a);
END.

Cliquez ici pour charger la version de Renaud Mercier.

2) Il est possible de déterminer le PGCD de 2 nombres naturels a et b en utilisant les propriétés suivantes:

  * si a=0:  PGCD(0,b) = b
    si b=0:  PGCD(a,0) = a
  * si a et b sont pairs: PGCD(a,b) = 2 * PGCD(a/2,b/2)
  * si a est pair et b impair: PGCD(a,b) = PGCD(a/2,b)
    si a est impair et b pair: PGCD(a,b) = PGCD(a,b/2)
  * si a et b sont impairs: PGCD(a,b) = PGCD(a-b,b) si a>b
                            PGCD(a,b) = PGCD(a,b-a) si b>a
entier a, b, PGCD

écrire "Introduisez le 1er nombre: "
lire a
écrire "Introduisez le 2ème nombre: "
lire b
tant que NOT (a*b=0) faire
  selon que
     a mod 2+b mod 2=0 faire PGCD <-- PGCD*2
                             a <-- a\2
                             b <-- b\2
  oq a mod 2+b mod 2=1 faire si a mod 2=0 alors a <-- a\2
                             sinon b <-- b\2
                             fsi
  oq a mod 2+b mod 2=2 faire si a>b alors a <-- a-b
                             sinon b <-- b-a
                             fsi
  fselon
ftant
si a=0 alors écrire "PGCD = ", PGCD*b
sinon écrire "PGCD = ", PGCD*a
fsi

VAR a,b,PGCD:LONGINT;

BEGIN
WRITE('Introduisez le 1er nombre: ');READLN(a);
WRITE('Introduisez le 2ème nombre: ');READLN(b);
PGCD:=1;
WHILE NOT (a*b=0) DO
  CASE a MOD 2+b MOD 2 OF
   0 : BEGIN
       PGCD:=PGCD SHL 1;{PGCD:=PGCD*2;}
       a:=a SHR 1;{a:=a DIV 2;}
       b:=b SHR 1;{b:=b DIV 2;}
       END;
   1 : IF a MOD 2=0 THEN a:=a SHR 1{a:=a DIV 2}
       ELSE b:=b SHR 1{b:=b DIV 2};
   2 : BEGIN
       IF a>b THEN a:=a-b
       ELSE b:=b-a
       END
  END;
IF a=0 THEN WRITELN ('PGCD=',PGCD*b)
ELSE WRITELN ('PGCD=',PGCD*a);
END.


3) Voici un autre algorithme de calcul du PGCD de 2 nombres naturels N1 et N2:

* assigner  N1 la valeur de N2 et  N2 la valeur du reste de la division de N1 par N2;
* recommencer jusqu' ce que le reste de la division soit nul. 
A ce moment, N1 contient le PGCD.
Exemple: si N1 vaut 14 et N2 vaut 32, on obtient successivement
N1			N2
14			32
32			14=14 mod 32
14			4=32 mod 14
4			2=14 mod 4
2			2=4 mod 2
2			0=2 mod 2

VAR N1,N2,Tmp:LONGINT;

BEGIN
WRITE('Introduisez le 1er nombre: ');READLN(N1);
WRITE('Introduisez le 2ème nombre: ');READLN(N2);
WHILE NOT (N2=0) DO
  BEGIN
  Tmp:=N1;
  N1:=N2;
  N2:=Tmp MOD N2; 
  END;
IF N1=0 THEN WRITELN('Pas de PGCD pour 2 nombres nuls!') 
ELSE WRITELN ('PGCD=',N1)
END.

Page précédente.
Page d'accueil.