Least Common Multiple

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

lcm(a, b) = a × b / gcd(a, b) , calculé sous la forme a / gcd(a, b) × b afin que la valeur intermédiaire ne dépasse jamais 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, la complexité est de O(log(min(a, b))) , soit le coût de l’algorithme d’Euclide, plus une division et une multiplication. Il nécessite un espace supplémentaire de O(1) . La recherche parmi les multiples est beaucoup plus lente : O(min(a, b)) si vous avancez par pas correspondant au plus grand nombre, et O(lcm(a, b)) si vous comptez de un en un.

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

Réduisez 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 : surveillez les dépassements de capacité et utilisez des entiers sur 64 bits lorsque la liste est longue.

DébutantMaths et simulation

+10

Vous recevez deux entiers positifs a et b. Renvoyez leur plus petit commun multiple : le plus petit entier positif qui est divisible par a et b sans reste.

Par exemple, les multiples de 6 sont 6, 12, 18, 24, etc., les multiples de 8 sont 8, 16, 24, etc., et le premier nombre commun aux deux listes est 24.

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 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 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 des 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 plus petit de 45 n’existe.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu trouver le pgcd sans utiliser du tout la division ni le reste, en utilisant uniquement la soustraction et la 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 les deux faces d’un même fait : gcd(a, b) × lcm(a, b) = a × b. La réponse rapide est donc a × b / gcd(a, b), à une réserve près. Le produit peut atteindre 10^12, ce qui provoque un dépassement de capacité d’un entier 32 bits même lorsque le résultat tient dans cette limite ; il faut donc diviser par le pgcd avant de multiplier.

Compter à partir du nombre le plus grand

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La réponse est un multiple des deux nombres, donc elle est au moins aussi grande que le plus grand des deux. Commence par définir un candidat m à max(a, b) et ajoute 1 jusqu’à ce que a et b le divisent tous les deux. Tu essaies les candidats dans l’ordre croissant, donc le premier qui convient est le plus petit.

Pour 4 et 6, tu essaies 6, 7, 8, 9, 10 et 11, qui ne conviennent pas, et tu t’arrêtes à 12. La boucle se termine toujours, car a × b est un multiple commun.

Le nombre d’essais est à peu près de l’ordre de grandeur de la réponse. Pour 46337 et 46327, deux nombres premiers, la réponse est 2146654199, donc la boucle s’exécute plus de deux milliards de fois. C’est beaucoup trop lent.

Algorithme

Définissez m comme la plus grande valeur entre a et b.
Tant que m % a ou m % b n'est pas égal à 0, ajoutez 1 à m.
Renvoyez 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 plupart des nombres candidats au décompte sont sans espoir : la réponse doit être un multiple du plus grand nombre, appelons-le big. Passe donc directement d’un multiple de big au suivant : big, 2 × big, 3 × big, et arrête-toi au premier que le plus petit nombre divise.

Pour 4 et 6, tu essaies 6 (4 ne le divise pas), puis 12 (il le divise). La réponse est k × big pour un certain k, et k est au plus égal au plus petit nombre, parce que small × big est toujours un multiple commun. La boucle s’exécute donc au plus min(a, b) fois, ce qui ne dépasse jamais un million ici.

C’est suffisamment rapide ici, mais le temps d’exécution augmente quand même avec la taille de l’entrée. Avec des nombres jusqu’à 10^18, ce ne serait pas le cas.

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.
Retournez 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. Le PGCD prend chaque facteur premier avec le plus petit de ses deux exposants, le PPCM prend le plus grand, et ensemble, ils utilisent une fois exactement chaque facteur de a et de b. On obtient ainsi gcd(a, b) × lcm(a, b) = a × b, donc lcm(a, b) = a × b / gcd(a, b). Pour 4 = 2² et 6 = 2 × 3, le PGCD est 2 et le PPCM est 2² × 3 = 12.

Trouvez le PGCD avec l'algorithme d'Euclide : remplacez (x, y) par (y, x % y) jusqu'à ce que y soit égal à 0. Cela prend O(log(min(a, b))) étapes.

Calculez ensuite a / gcd × b, dans cet ordre. Le PGCD divise a exactement, donc la division ne perd aucune précision, et le résultat ne dépasse jamais la réponse. Écrire plutôt a × b / gcd provoque un dépassement de capacité d'un entier 32 bits pour a = b = 10^6 : le produit vaut 10^12, alors que la réponse n'est que de 10^6.

Algorithme

Copiez a et b dans x et y.
Tant que y n’est pas égal à 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

La formule tient sur une ligne, et les bugs viennent de l’ordre des opérations arithmétiques.

Calculer a × b en premier. En Java, C, C++, C# et Rust, le produit de deux nombres proches de 10^6 dépasse la capacité d’un entier de 32 bits et le résultat est faux ou négatif (une compilation Rust en mode débogage déclenche plutôt une panique), même si le vrai ppcm tient dans un entier.
Diviser a × b par le pgcd en virgule flottante. Le résultat peut être 2.146654199E9 ou perdre ses derniers chiffres ; effectue tous les calculs avec des entiers.
Exécuter la boucle d’Euclide directement sur a et b, puis les utiliser dans la formule. Après la boucle, ils contiennent le pgcd et 0 : travaille donc sur des copies.
Supposer que la réponse est a × b. Ce n’est vrai que si les deux nombres n’ont aucun facteur en commun : lcm(4, 6) vaut 12, et non 24.

Questions fréquentes4

Quelle est la formule du PPCM de deux nombres ?

lcm(a, b) = a × b / gcd(a, b), calculé sous la forme a / gcd(a, b) × b afin que la valeur intermédiaire ne dépasse jamais le résultat. Pour 4 et 6, le PGCD est 2, et 4 / 2 × 6 = 12.

Pourquoi gcd(a, b) × lcm(a, b) est-il égal à a × b ?

Pour chaque nombre premier, le pgcd utilise la plus petite de ses puissances dans a et b, et le ppcm utilise la plus grande. La plus petite plus la plus grande correspond à la somme des deux puissances, qui est exactement la puissance de ce nombre premier dans a × b. Chaque nombre premier correspond, donc les deux produits sont égaux.

Quelle est la complexité temporelle du calcul du PPCM ?

Avec la formule du PGCD, la complexité est de O(log(min(a, b))), soit le coût de l’algorithme d’Euclide, plus une division et une multiplication. Il nécessite un espace supplémentaire de O(1). La recherche parmi les multiples est beaucoup plus lente : O(min(a, b)) si vous avancez par pas correspondant au plus grand nombre, et O(lcm(a, b)) si vous comptez de un en un.

Comment trouver le PPCM de plus de deux nombres ?

Réduisez 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 : surveillez les dépassements de capacité et utilisez des entiers sur 64 bits lorsque la liste est longue.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

a = 4
b = 6

Attendu

Least Common Multiple

Fonction

Contraintes

Exemples

Indices

Solution

Compter à partir du nombre le plus grand

Parcourir les multiples du plus grand nombre

Divisez par le PGCD, puis multipliez

Pièges et cas limites

Questions fréquentes4

Problèmes similaires