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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Властивості[ред.ред. код]

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

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

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

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

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

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

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

gcd — НСД