Найме́нше спі́льне кра́тне (НСК) двох цілих чисел — найменше натуральне число, яке є кратним обох цих чисел.
Властивості НСК(a, b) = НСК(b, a) (перестановка аргументів не змінює НСК);
НСК(a, b, c, d) = НСК(НСК(a, b), НСК(c, d));
НСК(a, b) = |ab|/НСД(a, b), де НСД(a, b) — найбільший спільний дільник чисел a, b.
Обчислення НСК методом розкладу на прості множники
Нехай розклад чисел на прості множники
Тоді НСК
Приклад Визначимо НСК. Розклад на прості множники:
або, подаючи для наочності нульові степені,
Отже, НСК
НСК можна теж обчислити за допомогою рівності НСК(a, b) =|ab|/НСД(a, b), використавши для обчислення НСД ефективний алгоритм Евкліда
Реалізація знаходження НСК(lcm) на C++
int lcm(int a, int b) { return (a*b) / gcd(a, b) ; } gcd — НСД
Джерела