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

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

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

Властивості

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

• НСК(a, b, c, d) = НСК(НСК(a, b), НСК(c, d));

• НСК(a, b) = |ab|/НСД(a, b), де НСД(a, b) — найбільший спільний дільник чисел a, b.

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

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

$a=2^{q_2}\cdot 3^{q_3}\cdot \dots \cdot p_k^{q_{p_k}};$

$b=2^{r_2}\cdot 3^{r_3}\cdot \dots \cdot p_k^{r_{p_k}}.$

Тоді

НСК$(a,b)=2^{\max (q_2;r_2)}\cdot 3^{\max (q_3;r_3)}\cdot \dots \cdot p_k^{\max (q_{p_k};r_{p_k})}.$

Приклад

Визначимо НСК$(840,396)$. Розклад на прості множники:

$840=2^3\cdot 3\cdot 5\cdot 7,$

$396=2^2\cdot 3^2\cdot 11;$

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

$840=2^3\cdot 3^1\cdot 5^1\cdot 7^1\cdot 11^0,$

$396=2^2\cdot 3^2\cdot 5^0\cdot 7^0\cdot 11^1.$

Отже,

НСК$(840,396)=2^3\cdot 3^2\cdot 5^1\cdot 7^1\cdot 11^1=27720.$

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

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

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

gcd — НСД

Джерела

• Шаблон:TAOCP.v2