|
== ==
'''Найменше спільне кратне''' (НСК) двох цілих чисел ''a'', ''b'' називаємо найменше [[натуральне число]], яке є кратним обох цих чисел. Позначаємо НСК(''a'', ''b''), в англомовній літературі LCM(''a'', ''b''). Отже НСК(''a'', ''b'') є найменшим натуральним числом, яке ділиться без залишку на обидва числа ''a'', ''b''.
Означення можна – очевидним способом – узагальнити на довільну кількість аргументів.
== Властивості ==
* НСК(''a'', ''b'')= НСК(''b'', ''a'') (перестановка аргументів не змінює НСК).
* НСК(''a'', ''b'', ''c'', ''d'') = НСК(НСК(''a'', ''b''), НСК(''c'', ''d'') )
* НСК(''a'', ''b'') =|ab|/НСД(''a'', ''b''), де НСД(''a'', ''b'') [[найбільший спільний дільник]] чисел ''a'', ''b''.
== Обчислення НСК методом розкладу на прості множники ==
Нехай [[Факторизація|розклад чисел на прості множники]]:
:<math>a=2^{q_2}\cdot 3^{q_3}\cdot \dots \cdot p_k^{q_{p_k}}</math>
:<math>b=2^{r_2}\cdot 3^{r_3}\cdot \dots \cdot p_k^{r_{p_k}}</math>
Тоді
:<big><big>НСК</big></big><math>(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})}</math>
=== Приклад ===
Визначимо <big>НСК</big><math>(840,396) </math>.
Розклад на прості множники:
:<math> 840 = 2^3 \cdot 3 \cdot 5 \cdot 7 </math>
:<math> 396 = 2^2 \cdot 3^2 \cdot 11 </math>,
або, подаючи для наочності нульові степені,
:<math> 840 = 2^3 \cdot 3^1 \cdot 5^1 \cdot 7^1 \cdot 11^0</math>
:<math> 396 = 2^2 \cdot 3^2 \cdot 5^0 \cdot 7^0 \cdot 11^1 </math>,
Отже,
:<big><big>НСК</big></big><math>(840,396)=2^3\cdot 3^2\cdot 5^1\cdot 7^1 \cdot 11^1=27720</math>
НСК можна теж обчислити за допомогою рівності НСК(''a'', ''b'') =|ab|/НСД(''a'', ''b''), використавши для обчислення НСД ефективний [[алгоритм Евкліда]]
== Реалізація знаходження НСК(lcm) на C++ ==
<source lang = "cpp">
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
</source>
gcd - [[НСД]]
[[Категорія:Елементарна математика]]
| 