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:

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:

Exemple:

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