GCD, LCM et algorithme d’Euclide
Calculer rapidement et correctement les diviseurs
GCD, LCM et algorithme d’Euclide est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Pourquoi les diviseurs sont importants
De nombreux problèmes de concours reposent sur les facteurs communs de deux nombres. L'outil le plus utile ici est le GCD, le plus grand commun diviseur. 🔢
Signification de GCD
Le GCD de deux entiers est le plus grand nombre qui divise les deux sans reste. Pour 12 et 18, c'est 6, puisque 6 divise exactement chacun d'eux.
La méthode lente
Vous pourriez essayer chaque nombre en partant de la plus petite valeur et en descendant jusqu'à en trouver un qui divise les deux. Cela fonctionne, mais c'est bien trop lent pour de grandes entrées.
L'idée euclidienne
L'algorithme d'Euclide est la méthode rapide. Son idée essentielle est la suivante : le GCD de a et b est égal au GCD de b et du reste de la division de a par b.
La récurrence
Répétez l'étape d'échange et de modulo jusqu'à ce que le reste soit nul. La dernière valeur non nulle restante est votre réponse, c'est-à-dire le GCD lui-même.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aCodez-le vous-même
Une courte boucle remplace la paire jusqu'à ce que b atteigne zéro. Elle s'exécute en environ log étapes, extrêmement rapidement même pour de très grands nombres.
def gcd(a, b):
while b:
a, b = b, a % b
return aUtilisez la bibliothèque standard
Vous aurez rarement besoin de l'implémenter vous-même. Python fournit math.gcd, qui est fiable, rapide et gère les arguments nuls à votre place.
from math import gcd
print(gcd(12, 18))Du GCD au LCM
Le LCM, ou plus petit commun multiple, est le plus petit nombre divisible par les deux valeurs. Il est directement lié au GCD que vous venez de calculer.
La formule du LCM
Multipliez les deux nombres, puis divisez par leur GCD. Effectuez toujours la division avant la multiplication pour éviter un dépassement de capacité avec de très grands produits.
def lcm(a, b):
return a // gcd(a, b) * bGCD d'une liste entière
Pour appliquer un GCD à de nombreux nombres, enchaînez les calculs deux à deux. La fonction Python reduce applique math.gcd de gauche à droite sur la liste.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Gérez le cas zéro
Par définition, gcd(a, 0) est égal à a, et gcd(0, 0) vaut 0. Connaître ce cas limite empêche vos boucles de mal fonctionner avec une entrée vide.
Vérification rapide
Il est temps de confirmer l'étape euclidienne essentielle.
Récapitulatif
Vous pouvez maintenant calculer le GCD avec l'algorithme d'Euclide en un nombre logarithmique d'étapes, en déduire le LCM et appliquer les deux opérations à une liste. ✅
Apprends Python avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 30
- Leçons
- 120
Questions Fréquemment Posées
La leçon « GCD, LCM et algorithme d’Euclide » est-elle gratuite ?
Oui — le texte complet de « GCD, LCM et algorithme d’Euclide » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « GCD, LCM et algorithme d’Euclide » ?
Calculer rapidement et correctement les diviseurs Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « GCD, LCM et algorithme d’Euclide » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- GCD, LCM et algorithme d’Euclide
- Tester la primalité jusqu’à sqrt(n)
- Crible d’Ératosthène
- Factorisation première et diviseurs