Наименьшее общее кратное (LCM)
Наименьшее общее кратное двух чисел
a и b — это наименьшее число, которое делится и на a, и на b. Иными словами, мы ищем число l (наименьшее общее кратное) такое, что и , где x и y — положительные целые числа (2 ≤ x, y).Наивным решением было бы перебирать последовательно все кратные
a (1·a, 2·a, 3·a и т.д.) и проверять, делится ли каждое из них на b. Однако это может занять слишком много времени. Представьте, что a и b равны 13 и 17. Тогда придётся проверить 1·13, 2·13 и так далее вплоть до 17·13, прежде чем мы дойдём до первого числа, которое делится и на 13, и на 17.Заметим, что произведение
a·b всегда будет общим кратным для a и b, но не обязательно наименьшим. В случае с 13 и 17 оно действительно окажется минимальным, однако, например, для 8 и 12 это не так. В общем случае, наименьшее общее кратное a и b равно произведению a и b, делённому на их наибольший общий делитель (gcd):Интуитивно это можно понять так: наименьшее общее кратное — это самое маленькое общее кратное, содержащее все простые множители обоих чисел. Поскольку наибольший общий делитель двух чисел — это произведение всех их общих простых множителей, то, деля произведение чисел на их gcd, мы «убираем» лишние повторения и получаем ровно наименьшее общее кратное.
Таким образом, чтобы найти наименьшее общее кратное двух чисел, сначала нужно разложить их на простые множители, а затем перемножить максимальные степени каждого простого числа, присутствующие хотя бы в одном из разложений.
В произведении
a·b оказываются все простые множители обоих чисел с суммарными степенями. Деление на gcd(a, b) убирает меньшую из степеней по каждому простому множителю, оставляя в точности то, что нужно для lcm(a, b).Входные данные
В единственной строке входных данных содержатся два целых числа
a и b (1 ≤ a, b ≤ ).Выходные данные
Программа должна вывести наименьшее общее кратное для
a и b.Примеры
Input | Output |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB