Calculer le PGCD avec l'algorithme d'Euclide en Python
Dans cette leçon, vous allez trouver le plus grand commun diviseur (PGCD) de deux nombres avec l'algorithme d'Euclide.
Introduction
Le problème
Simplifier des fractions, répartir des choses en groupes égaux et beaucoup d'énigmes demandent le plus grand nombre qui divise deux nombres. Essayer chaque candidat est lent pour de grands nombres ; Euclide a trouvé une méthode bien plus rapide il y a plus de 2 000 ans.
Imaginez-le ainsi
La méthode d'Euclide, c'est comme carreler un rectangle avec les plus grands carreaux carrés possibles. Découpez le plus grand carré possible dans un rectangle de 48 × 18, puis dans ce qui reste, et continuez. Quand les morceaux tombent juste sans reste, le côté du dernier carré est la réponse.
first, second▭ Le rectangle : 48 × 18first % second✂️ Ce qui reste après avoir découpé des carrés du petit côtéfirst, second = second, first % second🔁 Recommencer avec le morceau restantwhile second:✅ Plus de reste : le côté est le PGCD, 6Le plus grand commun diviseur (PGCD) de deux entiers est le plus grand entier positif qui les divise tous les deux ; l'algorithme d'Euclide le trouve en remplaçant la paire (a, b) par (b, a % b) jusqu'à ce que b vaille 0.
Points clés
first, second = second, first % secondremplace la paire par le plus petit nombre et le reste.- Pour 48 et 18, les paires sont (48, 18), (18, 12), (12, 6), (6, 0).
while second:s'arrête quand le reste devient 0.return abs(first)donne un résultat positif même pour des entrées négatives.
Quand l’utiliser ?
- Simplifier des fractions et des rapports.
- Trouver le plus petit commun multiple : a * b
//gcd(a, b). - Les énigmes sur les nombres, l'arithmétique modulaire et les bases de la cryptographie.
Quand s'en passer
- Le vrai code :
math.gcdest intégré et accepte n'importe quel nombre d'arguments dans les versions récentes de Python. - Trouver tous les diviseurs communs : le PGCD ne donne que le plus grand.
Code d’exemple
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
Résultat de l’exécution
6
Explication du code
À chaque étape, la paire (first, second) est remplacée par (second, first % second). Quand le reste vaut 0, la valeur restant dans first est le PGCD, celui de 48 et 18 est donc 6. La fonction abs() garantit que le résultat est toujours positif. Le nombre d'étapes augmente très lentement avec la taille des nombres, environ O(log n).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Utiliser la soustraction au lieu du reste
Des soustractions répétées donnent la même réponse mais sont très lentes pour des nombres très éloignés.
while first != second:
if first > second:
first -= second
else:
second -= first
while second:
first, second = second, first % second
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Plus grand commun diviseur Trouvez le plus grand nombre qui divise les deux valeurs. Facile
- Plus Petit Commun Multiple Trouvez le plus petit nombre positif divisible par les deux valeurs. Facile
- Arithmétique exacte des fractions Effectuez des opérations sur des fractions et retournez une fraction réduite. Moyen