Least Common Multiple

Q: Quelle est la formule du PPCM de deux nombres ?

lcm(a, b) = a × b / gcd(a, b) , calculé comme a / gcd(a, b) × b afin qu’aucune valeur intermédiaire ne dépasse le résultat. Pour 4 et 6 , le PGCD est 2 , et 4 / 2 × 6 = 12 .

Q: Quelle est la complexité temporelle du calcul du PPCM ?

Avec la formule du pgcd, le temps d’exécution est de O(log(min(a, b))) , soit le coût de l’algorithme d’Euclide, et l’espace requis est de O(1) . Parcourir les multiples du plus grand nombre prend O(min(a, b)) , et compter de un en un prend O(lcm(a, b)) .

Q: Comment trouver le PPCM de plus de deux nombres ?

Réduis la liste : lcm(a, b, c) = lcm(lcm(a, b), c) . Pour [4, 6, 10] , lcm(4, 6) = 12 et lcm(12, 10) = 60 . La valeur cumulée augmente rapidement ; utilise donc des entiers de 64 bits si la liste est longue.

DébutantMaths et simulation

+10

On te donne deux entiers positifs a et b. Renvoie leur plus petit commun multiple : le plus petit entier positif divisible par a et b sans reste.

Fonction

lcm(a: integer, b: integer) → integer

ainteger: le premier entier positif
binteger: le deuxième entier positif
Renvoieinteger: le plus petit entier positif qui est un multiple à la fois de a et de b

Contraintes

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
La réponse tient dans un entier signé de 32 bits : lcm(a, b) ≤ 2³¹-1. Le produit a × b peut ne pas y tenir.

Exemples

Entrée: a = 4b = 6
Sortie: 12
Explication: Les multiples de 6 commencent par 6, 12, 18 ; les multiples de 4 commencent par 4, 8, 12. Le premier nombre figurant sur les deux listes est 12.

Entrée: a = 7b = 3
Sortie: 21
Explication: 7 et 3 n’ont aucun facteur commun autre que 1, donc leur plus petit commun multiple est leur produit, 21.

Entrée: a = 15b = 45
Sortie: 45
Explication: 15 divise 45 exactement, donc 45 est déjà un multiple des deux, et aucun multiple de 45 plus petit n'existe.

Pour aller plus loin

Peux-tu trouver le pgcd sans utiliser de division ni de reste, uniquement par soustraction et division par deux ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Le plus petit commun multiple et le plus grand commun diviseur sont liés par une relation : gcd(a, b) × lcm(a, b) = a × b. La réponse rapide est donc a × b / gcd(a, b). Le produit peut atteindre 10^12 et dépasser la capacité d’un entier de 32 bits même si le résultat tient dans cette limite ; divise donc par le PGCD avant de multiplier.

Compte à partir du plus grand nombre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La réponse est au moins égale au plus grand nombre. Commencez avec m égal à max(a, b) et ajoutez 1 jusqu’à ce que les deux nombres le divisent ; vous essayez les candidats par ordre croissant, donc le premier résultat trouvé est le plus petit. Pour 4 et 6, vous essayez les nombres de 6 à 11 et vous vous arrêtez à 12. La boucle se termine toujours, car a × b est un multiple commun.

Le nombre d’essais est de l’ordre de la taille de la réponse. Pour les nombres premiers 46337 et 46327, la réponse est 2146654199, soit plus de deux milliards d’essais.

Algorithme

Définissez m comme étant la plus grande valeur de a et b.
Tant que m % a ou m % b n'est pas égal à 0, ajoutez 1 à m.
Retournez m.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Parcourir les multiples du plus grand nombre

Intuition

La réponse doit être un multiple du plus grand nombre, big ; avance donc par bonds de big, 2 × big, 3 × big, et arrête-toi au premier multiple divisible par le plus petit nombre. Pour 4 et 6, tu essaies 6, puis 12.

Puisque small × big est toujours un multiple commun, la boucle s’exécute au plus min(a, b) fois, soit au plus un million ici. C’est assez rapide pour ces limites, mais le nombre d’itérations augmente quand même avec la taille de l’entrée ; avec des nombres allant jusqu’à 10^18, cette méthode ne conviendrait pas.

Algorithme

Soit big le plus grand nombre et small le plus petit.
Définissez m = big.
Tant que m % small n’est pas égal à 0, ajoutez big à m.
Renvoyez m.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Divisez par le PGCD, puis multipliez

Intuition

Décomposez les deux nombres en facteurs premiers. Pour chaque nombre premier, le gcd prend la plus petite de ses deux puissances et le lcm la plus grande ; ensemble, ils utilisent ainsi chaque facteur de a et de b exactement une fois : gcd × lcm = a × b. Pour 4 = 2² et 6 = 2 × 3, le gcd vaut 2 et le lcm vaut 2² × 3 = 12.

L'algorithme d'Euclide trouve le gcd en O(log(min(a, b))) étapes. Calculez ensuite a / gcd × b dans cet ordre : le gcd divise a exactement, donc rien n'est perdu, et aucune étape ne dépasse la réponse. a × b / gcd provoque un dépassement de capacité d'un entier 32 bits lorsque a = b = 10^6, car le produit vaut 10^12 alors que la réponse ne vaut que 10^6.

Algorithme

Copiez a et b dans x et y.
Tant que y n’est pas 0, remplacez (x, y) par (y, x % y). À présent, x est le pgcd.
Divisez a par x.
Multipliez le résultat par b et renvoyez-le.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

Pièges et cas limites

Calculer d’abord a × b. En Java, C, C++, C# et Rust, le produit de deux nombres proches de 10^6 dépasse la capacité d’un entier signé sur 32 bits et donne un résultat incorrect ou négatif (une compilation de débogage Rust provoque une panique), même si le ppcm tient dans cette capacité.
Effectuer la division en virgule flottante. Le résultat peut être 2.146654199E9 ou perdre ses derniers chiffres ; gardez tout en nombres entiers.
Exécuter la boucle d’Euclide directement sur a et b. À la fin, ils contiennent le pgcd et 0 ; travaillez donc sur des copies.
Supposer que la réponse est a × b. Ce n’est vrai que lorsque les nombres n’ont aucun facteur commun : lcm(4, 6) vaut 12, et non 24.

Questions fréquentes3

Quelle est la formule du PPCM de deux nombres ?

lcm(a, b) = a × b / gcd(a, b), calculé comme a / gcd(a, b) × b afin qu’aucune valeur intermédiaire ne dépasse le résultat. Pour 4 et 6, le PGCD est 2, et 4 / 2 × 6 = 12.

Quelle est la complexité temporelle du calcul du PPCM ?

Avec la formule du pgcd, le temps d’exécution est de O(log(min(a, b))), soit le coût de l’algorithme d’Euclide, et l’espace requis est de O(1). Parcourir les multiples du plus grand nombre prend O(min(a, b)), et compter de un en un prend O(lcm(a, b)).

Comment trouver le PPCM de plus de deux nombres ?

Réduis la liste : lcm(a, b, c) = lcm(lcm(a, b), c). Pour [4, 6, 10], lcm(4, 6) = 12 et lcm(12, 10) = 60. La valeur cumulée augmente rapidement ; utilise donc des entiers de 64 bits si la liste est longue.

def lcm(a, b):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

a = 4
b = 6

Résultat attendu

Least Common Multiple

Fonction

Contraintes

Exemples

Indices

Solution

Compte à partir du plus grand nombre

Parcourir les multiples du plus grand nombre

Divisez par le PGCD, puis multipliez

Pièges et cas limites

Questions fréquentes3

Problèmes similaires