ЯК знайти нод і нок чисел :: як знайти числа нок яких є 120

Цілі числа - безліч математичних чисел, що мають велике застосування в повсякденному житті. Невід'ємні цілі числа використовуються при вказівці кількості будь-яких об'єктів, негативні числа - в повідомленнях про прогноз погоди та ін. НОД і НОК - це натуральні характеристики цілих чисел, пов'язані з операціями поділу.

Інструкція

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

НОД легко обчислити за алгоритмом Евкліда або бінарним методом. За алгоритмом Евкліда визначення НОД чисел a і b, одне з яких не дорівнює нулю, існує така послідовність чисел r_1> r_2> r_3> ...> r_n, в якій елемент r_1 дорівнює залишку від ділення першого числа на друге. А інші члени послідовності рівні залишкам від ділення предпредидущего члена на попередній, а передостанній елемент ділиться на останній без залишку.

Математично послідовність можна представити у вигляді:
a = b * k_0 + r_1
b = r_1 * k_1 + r_2
r_1 = r_2 * k_2 + r_3
...
r_ (n - 1) = r_n * k_n,
де k_i - цілочисельний множник.
НОД (a, b) = r_n.

Алгоритм Евкліда називають взаємним відніманням, оскільки НСД виходить при послідовному відніманні меншого з більшого. Неважко припустити, що НОД (a, b) = НСД (b, r).

Приклад.
Знайдіть НСД (36, 120). За алгоритмом Евкліда відніміть від 120 число, кратне 36, в даному випадку це 120 - 36 * 3 = 12. Тепер відніміть від 120 число, кратне 12, вийде 120 - 12 * 10 = 0. Отже, НОД (36, 120) = 12.

Бінарний алгоритм знаходження НСД заснований на теорії зсуву. Відповідно до цього методу НСД двох чисел має такі властивості:
НОД (a, b) = 2 * НОД (a / 2, b / 2) для парних a і b
НОД (a, b) = НСД (a / 2, b) для парного a і непарного b (навпаки вірно НОД (a, b) = НСД (a, b / 2))
НОД (a, b) = НСД ((a - b) / 2, b) для непарних a> b
НОД (a, b) = НСД ((b - a) / 2, a) для непарних b> a
Таким чином, НОД (36, 120) = 2 * НОД (18, 60) = 4 * НОД (9, 30) = 4 * НОД (9, 15) = 4 * НОД ((15 - 9) / 2 = 3 , 9) = 4 * 3 = 12.

Найменше спільне кратне (НОК) двох цілих чисел - це найменше ціле число, яке ділиться на обидва вихідних числа без залишку.
НОК можна обчислити через НОД: НОК (a, b) = | a * b | / НОД (a, b).

Другий спосіб обчислення НОК - канонічне розкладання чисел на прості множники:
a = r_1 ^ k_1 * ... * r_n ^ k_n
b = r_1 ^ m_1 * ... * r_n ^ m_n,
де r_i - прості числа, а k_i і m_i - цілі числа? 0.
НОК представляється у вигляді тих же простих множників, де в якості ступенів беруться максимальні з двох чисел.

Приклад.
Знайдіть НОК (16, 20):
16 = 2 ^ 4 * 3 ^ 0 * 5 ^ 0
20 = 2 ^ 2 * 3 ^ 0 * 5 ^ 1
НОК (16, 20) = 2 ^ 4 * 3 ^ 0 * 5 ^ 1 = 16 * 5 = 80.