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

Запис числа в виді добутку простих чисел називається розкладом цього числа на прості множники. Наприклад, 110=2*5*11. розкладаючи числа на прості множники, використовують ознаки подільності на 2,3,,5,7, 11,13,17…наприклад, число 720=2*2*2*23*3*5=, або і .

В розклад на прості множники НСД мають ввійти всі спільні прості множники, які містяться в розкладі даних чисел, причому кожний з них потрібно взяти з найменшим степенем, з яким вони входять в обидва розклади. Тоді .

В розклад на прості множники НСК мають ввійти всі спільні прості множники, які містяться хоча б одному з розкладів даних чисел, причому кожний з них потрібно взяти з найбільшим степенем, з яким вони входять в обидва розклади. Тоді .

Алгоритм знаходження НСК, НСД.

1. представляємо число в канонічному виді.

2. Утворюємо добуток спільних для чисел простих множників, причому кожний х них обираємо з найменшим степенем, з яким вони входять до розкладу. Обчислюємо значення добутку – це НСД даних чисел.

3. утворюємо добуток з всіх простих множників, причому кожний обираємо з найбільшим степенем, з яким вони входять до розкладу чисел. Обчислюємо значення добутку – це НСК цих чисел.

Наприклад, знайти НСД і НСК чисел 60, 252, 264.

Дата добавления: 2014-01-07