PGCD — Algorithme d'Euclide

Algorithmique classique

Exercice Débutant · Algo Express · prepa scientifique et economique (CPGE)

Enonce

Calculer le PGCD de deux entiers positifs par l'algorithme d'Euclide.

Signature attendue

def pgcd(a: int, b: int) -> int:

Exemples

pgcd(48, 18) → 6
pgcd(100, 75) → 25

📖 Rappel de cours

Tant que b n'est pas nul, on remplace le couple (a, b) par (b, a % b). Le PGCD est le dernier a non nul.

⚠ Le piège : L'invariant est que pgcd(a, b) ne change jamais au cours des remplacements — c'est lui qui justifie l'algorithme, et il vaut souvent des points de l'écrire.

← Exercices Python pour la prépa — CPGE scientifique et ECG

Exercices du meme theme

Nombre de Voyelles
Vérifier si Premier
Liste des Diviseurs
Nombre de Mots
Compter les Majuscules
Indices de toutes les Occurrences

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.