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

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

Зміст

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

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

Правило знаходження НСКРедагувати

Щоб знайти НСК двох чисел:

  1. Розкладіть дані числа на прості множники.
  2. Запишіть розклад одного з даних чисел.
  3. Допишіть до цього розкладу такі множники із розкладу іншого числа, які ще не увійшли до добутку.
  4. Обчисліть отриманий добуток.

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

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

 
 

Тоді

НСК 

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

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

 
 

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

 
 

Отже,

НСК 

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

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

1 int lcm(int a, int b)
2 {
3   return (a*b) / gcd(a, b) ;
4 }

gcd — НСД