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

Найменше натуральне число, яке є кратним даних чисел

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

Діаграма Венна зображає найменші спільні кратні для комбінацій із чисел 2, 3, 4, 5 і 7 (6 відсутнє, оскільки 2 × 3, обидва з яких уже представлені).
Наприклад, у грі в карти до 5 гравців, в якій необхідно порівну розділити карти, потребує мати в колоді принаймні 60 карт, це те число, яке є перетином для множин 2, 3, 4, і 5, але не для 7.

ВластивостіРедагувати

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

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

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

 
 

Тоді

НСК 

ПрикладРедагувати

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

 
 

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

 
 

Отже,

НСК 

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

Реалізація знаходження НСК(lcm) на C++Редагувати

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

gcd — НСД