Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

Du découpage de carrés au code
first, second▭ Le rectangle : 48 × 18
first % 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 restant
while second:✅ Plus de reste : le côté est le PGCD, 6
gcd(a, b) = gcd(b, a % b) jusqu'à un reste nul.
En une phrase

Le 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

  1. first, second = second, first % second remplace la paire par le plus petit nombre et le reste.
  2. Pour 48 et 18, les paires sont (48, 18), (18, 12), (12, 6), (6, 0).
  3. while second: s'arrête quand le reste devient 0.
  4. 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.gcd est 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

Exécuter le code →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

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.

Problème
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
Correction
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.

Tous les défis