Le PGCD, (ou plus grand commun diviseur), de deux entiers strictement positifs \(a\) et \(b\) est le plus grand entier positif qui divise \(a\) et \(b\).
Le PGCD de \(18\) et \(24\) est \(6\) ;
Le PGCD de \(20\) et \(10\) est \(10\) ;
Le PGCD de \(28\) et \(15\) est \(1\).
Division euclidienne
Si \(a\) et \(b\) sont deux entiers strictement positifs, effectuer la division euclidienne de \(a\) par \(b\) consiste à trouver deux entiers positifs \(q\) et \(r\) (appelés respectivement le quotient et le reste) tels que \(a = bq + r\) et \(0\leq r < b\).
Avec Python le reste \(r\) est la valeur de l'expression a%b.
On demande dans cet exercice d'écrire la fonction pgcd qui prend en paramètres deux entiers strictement positifs a et b et renvoie le PGCD de ces deux nombres.
Deux versions, l'une itérative et l'autre récursive, sont proposées.
Exemples
>>> pgcd(18,24)6>>> pgcd(20,10)10>>> pgcd(28,15)1
Fonction gcd interdite
Le module math propose une fonction calculant le PGCD de deux entiers.
On s'interdit d'utiliser cette fonction dans cet exercice.
Version itérative
On utilise l'algorithme d'Euclide avec \(a\) et \(b\) deux entiers strictement positifs.
On détermine le reste \(r\) dans la division euclidienne de \(a\) par \(b\).
Tant que \(r\) n'est pas nul, \(a\) prend la valeur de \(b\), \(b\) prend la valeur de \(r\) et on calcule le nouveau reste \(r\) dans la division euclidienne de \(a\) par \(b\).
L'algorithme est terminé, le reste \(r\) est nul, et le PGCD est \(b\).
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)