Найменше спільне кратне

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Найменше спільне кратне (НСК) двох цілих чисел ab називаємо найменше натуральне число, яке є кратним обох цих чисел. Позначаємо НСК(ab), в англомовній літературі LCM(ab). Отже НСК(ab) є найменшим натуральним числом, яке ділиться без залишку на обидва числа ab. Означення можна — очевидним способом — узагальнити на довільну кількість аргументів.

Властивості[ред.ред. код]

  • НСК(ab)= НСК(ba) (перестановка аргументів не змінює НСК).
  • НСК(abcd) = НСК(НСК(ab), НСК(cd))

Обчислення НСК методом розкладу на прості множники[ред.ред. код]

Нехай розклад чисел на прості множники:

Тоді

НСК

Приклад[ред.ред. код]

Визначимо НСК. Розклад на прості множники:

,

або, подаючи для наочності нульові степені,

,

Отже,

НСК

НСК можна теж обчислити за допомогою рівності НСК(ab) =|ab|/НСД(ab), використавши для обчислення НСД ефективний алгоритм Евклідаеепвчспа

Реалізація знаходження НСК(lcm) на C++[ред.ред. код]

int lcm(int a, int b)
{
  return a / gcd(a, b) * b;
}

gcd — НСД