Наименьший общий делитель

Question

Наименьший общий делитель

Максим Швалев Ученик (96), закрыт 7 месяцев назад

Помогите я не понимаю, почему в некоторых примеров НОД мы выписываем всё повторяющийся числа а в не которых нет допустим 24 и 54 мы выписываем только 2,3 а не 2,2,3,3

Answer 1

Для нахождения наибольшего общего делителя (НОД) двух чисел используется алгоритм Евклида. Согласно этому алгоритму, мы последовательно делим большее число на меньшее, пока одно из них не станет равным нулю. Остаток от деления в каждом шаге сохраняется и используется в следующем шаге.

Пример: НОД(24, 54)

Делим 54 на 24: 54 / 24 = 2, остаток 10
Делим 24 на 10: 24 / 10 = 2, остаток 4
Делим 10 на 4: 10 / 4 = 2,5, округление вниз дает 2, остаток 2
Делим 4 на 2: 4 / 2 = 2, остатка нет

Здесь видим, что последним остатком является 2, который является общим делителем для обоих чисел. Это значит, что НОД(24, 54) = 2.

Таким образом, мы выписываем только последние повторяющиеся числа, потому что они являются общими делителями.

Answer 2

Richard Kruspe Гуру (3782) 7 месяцев назад

А я че, я гуманитарий

Answer 3

Недавно отвечала, сейчас уже ответ ушёл по горизонт. Ещё раз:
мы должны выбрать не просто рандомное или максимальное число общих делителей, а именно, наибольшее повторяющееся и в первом и во втором разложении. К примеру:
66=3*2*11
88=2*2*11
Выбираем 2*11 (11 встречается по 1 разу, а 2 встречается МИНИМАЛЬНО 1 раз)
Можно ещё для наглядности вычёркивать делители, но только парами: 11 в первом и во втором, 2 в первом и во втором, для ещё одной двойки во втором числе пары нет, так же как и для тройки в первом