Матеріал з Вікіпедії — вільної енциклопедії.
Діаграма Венна зображає найменші спільні кратні для комбінацій із чисел 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
=
2
q
2
⋅
3
q
3
⋅
…
⋅
p
k
q
p
k
;
{\displaystyle a=2^{q_{2}}\cdot 3^{q_{3}}\cdot \ldots \cdot p_{k}^{q_{p_{k}}};}
b
=
2
r
2
⋅
3
r
3
⋅
…
⋅
p
k
r
p
k
.
{\displaystyle b=2^{r_{2}}\cdot 3^{r_{3}}\cdot \ldots \cdot p_{k}^{r_{p_{k}}}.}
Тоді
НСК
(
a
,
b
)
=
2
max
(
q
2
;
r
2
)
⋅
3
max
(
q
3
;
r
3
)
⋅
⋯
⋅
p
k
max
(
q
p
k
;
r
p
k
)
.
{\displaystyle (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
)
{\displaystyle (840,396)}
.
Розклад на прості множники:
840
=
2
3
⋅
3
⋅
5
⋅
7
,
{\displaystyle 840=2^{3}\cdot 3\cdot 5\cdot 7,}
396
=
2
2
⋅
3
2
⋅
11
;
{\displaystyle 396=2^{2}\cdot 3^{2}\cdot 11;}
або, подаючи для наочності нульові степені,
840
=
2
3
⋅
3
1
⋅
5
1
⋅
7
1
⋅
11
0
,
{\displaystyle 840=2^{3}\cdot 3^{1}\cdot 5^{1}\cdot 7^{1}\cdot 11^{0},}
396
=
2
2
⋅
3
2
⋅
5
0
⋅
7
0
⋅
11
1
.
{\displaystyle 396=2^{2}\cdot 3^{2}\cdot 5^{0}\cdot 7^{0}\cdot 11^{1}.}
Отже,
НСК
(
840
,
396
)
=
2
3
⋅
3
2
⋅
5
1
⋅
7
1
⋅
11
1
=
27720.
{\displaystyle (840,396)=2^{3}\cdot 3^{2}\cdot 5^{1}\cdot 7^{1}\cdot 11^{1}=27720.}
НСК можна теж обчислити за допомогою рівності НСК(a , b ) =|ab|/НСД(a , b ), використавши для обчислення НСД ефективний алгоритм Евкліда
int lcm ( int a , int b )
{
return ( a * b ) / gcd ( a , b ) ;
}
gcd — НСД