Kleinstes gemeinsames Vielfaches (LCM)
Das kleinste gemeinsame Vielfache von zwei Zahlen
a und b ist die kleinste Zahl, die sowohl durch a als auch durch b teilbar ist. Wir können also eine Zahl l (least common multiple, kurz LCM) finden, für die gilt und , wobei x und y positive ganze Zahlen sind (2 ≤ x, y).Ein naiver Ansatz wäre, nacheinander die Vielfachen von
a (also 1·a, 2·a, 3·a, …) zu untersuchen und zu prüfen, ob eines davon auch durch b teilbar ist. Das kann jedoch sehr lange dauern. Angenommen, a und b sind 13 und 17 – dann müsste man bis zu 17·13 gehen, um schließlich eine Zahl zu finden, die beide teilt.Wir wissen allerdings, dass
a·b immer ein gemeinsames Vielfaches von a und b ist, jedoch nicht unbedingt das kleinste. Bei 13 und 17 war es tatsächlich das kleinste gemeinsame Vielfache, aber bei anderen Zahlen wie 8 und 12 ist das nicht der Fall. Allgemein gilt jedoch:Grundlage für diese Formel ist die Beobachtung, dass das kleinste gemeinsame Vielfache genau das kleinste gemeinsame Produkt beider Zahlen ist, in dem alle gemeinsamen Primfaktoren enthalten sind. Da der größte gemeinsame Teiler von zwei Zahlen das Produkt aus allen gemeinsamen Primfaktoren ist, können wir, indem wir das Produkt
a·b durch den gcd dividieren, die doppelt gezählten Faktoren entfernen und landen genau beim LCM.Um das LCM (kleinstes gemeinsames Vielfaches) zweier Zahlen zu ermitteln, bestimmt man zunächst die Primfaktorzerlegung beider Zahlen und multipliziert anschließend die maximalen Exponenten jedes auftretenden Primfaktors.
Wenn wir das Produkt
a·b betrachten, enthält es alle Primfaktoren von a und b in jeweils addierter Exponentenzahl. Dividiert man dieses Produkt durch gcd(a, b), entfernt man genau die minimalen Exponenten der gemeinsamen Faktoren und behält somit die maximalen Exponenten jedes Faktors – das Resultat ist das LCM von a und b.Eingabe
Die einzige Zeile der Eingabe enthält zwei ganze Zahlen
a und b (1 ≤ a, b ≤ ).Ausgabe
Das Programm soll das kleinste gemeinsame Vielfache von
a und b ausgeben.Beispiele
Eingabe | Ausgabe |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB