Le plus petit commun multiple (LCM)
Le plus petit commun multiple (LCM) de deux nombres
a et b est le plus petit nombre qui soit divisible à la fois par a et par b. Autrement dit, on peut trouver un nombre l (le plus petit commun multiple) tel que et , où x et y sont des entiers positifs (2 ≤ x, y).Une approche naïve consisterait à parcourir les multiples de
a (1·a, 2·a, 3·a, …) et à vérifier si chacun d’entre eux est divisible par b. Toutefois, cela peut être très long. Imaginez si a et b valent 13 et 17 : on devrait calculer 1·13, 2·13, …, jusqu’à 17·13 pour enfin tomber sur un multiple commun à 13 et 17.En réalité, on constate que
a·b est toujours un multiple commun de a et b. Cependant, ce n’est pas nécessairement le plus petit. Dans le cas de 13 et 17, a·b correspond au plus petit commun multiple, mais pour d’autres cas, comme 8 et 12, ce ne sera pas le cas. En général, le LCM de a et b est égal au produit de a et b divisé par leur plus grand commun diviseur :L’idée derrière cette formule est que le LCM est le plus petit multiple des deux nombres qui rassemble tous leurs facteurs premiers communs. Or, puisque le plus grand commun diviseur de deux nombres est justement le produit de leurs facteurs premiers communs, on obtient le LCM en divisant le produit des deux nombres par ce plus grand commun diviseur, afin de retirer les facteurs en double.
Pour trouver le LCM de deux nombres, on fait donc la factorisation en nombres premiers de chacun, puis on multiplie la plus grande puissance de chaque facteur premier apparaissant dans l’une ou l’autre factorisation.
Dans cette optique, le produit
a·b réunit tous les facteurs premiers de a et de b en additionnant leurs exposants. Ensuite, gcd(a, b) enlève la plus petite puissance pour chacun de ces facteurs, ce qui laisse la plus grande, et permet finalement d’obtenir exactement le LCM de a et b.Entrée
La seule ligne de l’entrée contient deux entiers
a et b (1 ≤ a, b ≤ ).Sortie
Le programme doit afficher le plus petit commun multiple de
a et b.Exemples
Input | Output |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB