1) Voici un algorithme, dû à Euclide, qui détermine le PGCD de 2 nombres
naturels a et b.
Cliquez ici pour charger la version de Renaud Mercier.
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.
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.