Calculer le PGCD

Exercice - niveau basique¶

On vous demande d’écrire une fonction qui calcule le PGCD de deux entiers, en utilisant l’algorithme d’Euclide.

Les deux paramètres sont supposés être des entiers positifs ou nuls (pas la peine de le vérifier).

Dans le cas où un des deux paramètres est nul, le PGCD vaut l’autre paramètre. Ainsi par exemple:

from corrections.exo_pgcd import exo_pgcd
exo_pgcd.example()

Remarque on peut tout à fait utiliser une fonction récursive pour implémenter l’algorithme d’Euclide. Par exemple cette version de pgcd fonctionne très bien aussi (en supposant a>=b)

def pgcd(a, b):
    "Le PGCD avec une fonction récursive"
    if not b:
        return a
    return pgcd(b, a % b)

Cependant, il vous est demandé ici d’utiliser une boucle while, qui est le sujet de la séquence, pour implémenter pgcd.

# à vous de jouer
def pgcd(a, b):
    "<votre code>"

# pour vérifier votre code
exo_pgcd.correction(pgcd)