Calcul récursif de PGCD en langage C

Le PGCD (plus grand commun diviseur) de deux nombre entiers quand au moins l'un des deux n'égale pas à zéro est le plus grand diviseur entier positive qui divise deux nombres. Par exemple, le PGCD de 45 et 30 est 15.

1- Trouver le PGCD en utilisant le Modulo

  • Affecter à a la valeur de b et à b la valeur du reste de la division de a sur b.
  • Recommencer jusqu'à ce que le reste soit égale à zéro.
pgcd modulo Algorithme d'Euclide étendu C++

Exemple:
Exemple PGCD Modulo Algorithme d'Euclide étendu
Le programme correspondant en C:

#include<stdio.h>

int main()
{
int a,b,r,x,y;
do
scanf("%d",&a);
while (a<=0);
do
scanf("%d",&b);
while (b<=0);

if (a>b)
{
x=b;
r=a%b;
}
else
{
x=a;
r=b%a;
}

while(r!=0)
{
y=x;
x=r;
r=y%x;
}
printf("%d",x);
return 0;
}

2- Trouver le PGCD avec la méthode soustractive récursif

Si a et b étant deux entiers positifs, on a les propriétés arithmétiques suivantes:
PGCD soustractive récursif
Exemple:
Exeple de PGCD soustractive récursif

Programme de PGCD avec récursivité.

int PGCD(int a, int b)
{
if(a==b)
{
return a;
}
else
{
if(a>b)
return PGCD(a-b, b);
else
return PGCD(a, b-a);
}
}
Références:
Wikipédia: Plus grand commun diviseur
Wikipédia: Algorithme d'Euclide étendu