Source : Ahmed Fessi

Tâche : Ecrire une fonction qui renvoie PGCD(a,b) en utilsant l'algorithme d'Euclide (méthode par division).

Commentaire

• PGCD : Plus Grand Diviseur Commun
• Algorithme d'Euclide (Division) : PGCD (a,b) = PGCD (b,r) avec r = a mod b

Exemple :

• Entrée : a=18, b=24
• Sortie : PGCD(18,24)=6

Correction : Par Ahmed Fessi

En Pseudo Code  :

Fonction PGCD(a:nombre, b:nombre):nombre
Si b=0
| alors PGCD=a
Sinon
| r egal au reste de la division (entière) de a par b
| PGCD=PGCD(b, r)
Finsi 

En C:

int pgcd(int m, int n)
 {
   if (n == 0)
   {
      return m;
   } else {
      return pgcd(n, m%n);

    }
 } 

En PHP :

function pgcd($a, $b)
{
    for($c = $a % $b ; $c != 0 ; $c = $a % $b) 
    {
        $a = $b;
        $b = $c;
    }
 
return $b;
}