Как найти наибольший общий делитель ~ Инструкции на все случаи жизни

Делитель натурального числа a — это такое натуральное число, которое делит данное число «a» без остатка.

Наибольший общий делитель или НОД для двух чисел, обозначим их А и В, представляет собой наибольших из совокупности общих делителей А и В. Например, возьмем два числа: 27 и 9. НОД для этой числовой пары будет равен 9.
НОД можно найти, и он существует только в том случае, если хотя бы одно из чисел пары, то есть А и В, не равно нулю. При обозначения данного показателя принято писать НОД (А, В), при этом вместо букв А и В прописываются числа, с которыми мы работаем.
Рассматриваемый показатель можно применить и найти для любого набора, при условии, что числовая пара состоит из целых чисел. Основная сфера применения – сокращение дробей: если правильно найти НОД дробных знаменателя и числителя, на полученную цифру можно сократить дробный знаменатель и числитель.
Наименьшее общее кратное или НОК для двух натуральных чисел Х и У представляет собой наименьшее число, на которое выбранные Х и У могут делиться полностью, не образуя остаток в результате вычислений. Например, возьмем два числа: 50 и 35. НОК для выбранной цифровой пары составит 350. Чаще всего НОК рассчитывают для приведения дробей к общему знаменателю.
При обозначении данного показателя, как и предыдущего показателя, принято писать НОК (Х, У), при этом вместо букв Х и У указываются числа, с которыми мы производим вычисления.

Рассматривая теоретический аспект, как работают онлайн калькуляторы НОК и НОД чисел, необходимо изучить, как можно определить, делится ли одно число на другое или нет. Для этого нужно использовать признаки и свойства делимости чисел. Сочетая и комбинируя их, можно быстро и просто осуществлять проверку делимости на некоторые цифры или их сочетания. Рассмотрим признаки делимости наиболее часто используемых чисел:
1. На «2». Чтобы выявить, делится ли число на «2», то есть является ли оно четным или нечетным, необходимо учесть ее последнюю цифру. Если число заканчивается на «8», «4», «2», и «0», оно является четным и должно поделиться на «2». К примеру, нужно определить, делится ли 45674 на «2». Ответ: так как число заканчивается на «4», оно является четным и делится на «2».
2. На «3». Число будет без остатка делиться на «3» при условии, что сумма всех цифр, образующих число, будет делиться на «3» без остатка. Если данное действие не позволило ответить на поставленный вопрос, так как результат получился слишком большим, необходимо вновь повторить данное действие. К примеру, нужно найти, делится ли 369785 на «3». Выполняем складывание: 3+6+9+7+8+5=38. Далее складываем 3+8=11. «11» не делится на «3», поэтому и число 369785 не делится на «3», не образуя остаток.
3. На «5». Чтобы число делилось на «5» полностью, без остатка, оно должно заканчиваться на «0» или на цифру «5». К примеру, нужно выявить, делится ли 569785 на «5». Так как число заканчивается на цифру 5, оно делится на «5».
4. На «9». В данном случае используем тот же алгоритм действий, что и для цифры «3». К примеру, нам нужно определить, делится ли 123456 на 9. Сначала выполняем складывание: 1+2+3+4+5+6= 21. 21 не делится на «9», следовательно и 123456 не делится на «9». Если бы в результате вычислений мы получили большое число, так же, как и с тройкой, сначала бы выполнили сложение, а затем деление на «9».

Сначала разберем, как определить наибольший общий делитель двух натуральных чисел. В данном случае наиболее удобным и простым способом является подбор всех возможных делителей выбранной числовой пары и определение наибольшего из найденных чисел.

Чтобы лучше понять, рассмотрим пример:

найдем НОД (36, 28).

Первым шагом будет разложение выбранных чисел на множители: 36=1*2*2*3*3, 28= 1*2*2*7. Отмечаем, какие из полученных множителей являются общими, то есть встречаются и при разложении 36 и при разложении 28. Это 1,2 и 2. Теперь находим произведение выявленных общих множителей, то есть умножаем их между собой и получаем в результате умножения 4.

Таким образом, НОД для указанной числовой паре будет равен 4.

Допустим, нам даны два целых числа числа, которые мы обозначим как У1 и У2. Нам требуется найти НОД, то есть такое число Х, которое бы одновременно делило бы У1 и У2. Рассмотрим данный алгоритм более подробно.

Пусть У1 ≥ У2 и при этом У1= n1У2+У3. При этом n1 и У3 являются целыми числами, а У3

Отказ от ответственности

Все калькуляторы и расчеты размещены исключительно в ознакомительных целях.

Администрация не несет ответственности за правильность результата.

В данной статье мы рассмотрим определение наибольшего общего делителя, научимся его находить для двух или нескольких чисел, а также разберем практические примеры для закрепления изложенного материала.

Определение наибольшего общего делителя
Нахождение НОД
- Для двух (или небольших) чисел
- Для нескольких (или больших) чисел

Определение наибольшего общего делителя

Делитель натурального числа a – это такое натуральное число b , которое делит a нацело (без остатка). Обозначается буквой Д. Например Д(6) означает “делитель числа 6”.

Если у числа больше двух делителей, его называют составным.

Число 12 имеет следующие делители: 1, 2, 3, 4, 6.
Число 15 имеет следующие делители: 1, 3, 5.

В отличие от кратных, количество делителей числа ограничено.

Общий делитель двух натуральных чисел – это такое число, на которое оба этих числа делятся без остатка.

Наибольший общий делитель двух натуральных чисел – наибольшее число из общих делителей данных чисел. Обозначается как НОД.

Например, НОД (12, 24) – это наибольший общий делитель чисел 12 и 24.

Нахождение НОД

Чтобы найти наибольший общий делитель, можно применить один из способов ниже.

Для двух (или небольших) чисел

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

Пример
Найдем наибольший делитель чисел 18 и 30.

Решение
Д(18): 1, 2, 3, 6 , 9.
Д(30): 1, 2, 3, 5, 6 , 10, 15.

Таким образом, НОД (18, 30) = 6.

Для нескольких (или больших) чисел

Этот метод обычно применяется, если приходится иметь дело с большим числами, или нужно найти НОД для нескольких чисел.

Пример
Найдем НОД (16, 24, 40).

Решение
Разложим эти числа на простые множители.

Для всех трех чисел одинаковыми являются три множителя – это три двойки.

Следовательно, НОД (16, 24, 40) = 2 ⋅ 2 ⋅ 2 = 8.

Делитель натурального числа a — это такое натуральное число, которое делит данное число «a» без остатка.

Чтобы лучше понять, рассмотрим пример:

найдем НОД (36, 28).

Таким образом, НОД для указанной числовой паре будет равен 4.

Пусть У1 ≥ У2 и при этом У1= n1У2+У3. При этом n1 и У3 являются целыми числами, а У3

Отказ от ответственности

Все калькуляторы и расчеты размещены исключительно в ознакомительных целях.

Администрация не несет ответственности за правильность результата.

Что такое НОК и НОД двух натуральных чисел
Особенности вычисления, алгоритм Евклида
Правило нахождения наибольшего общего делителя (НОД)
Правило нахождения наименьшего общего кратного (НОК)

Что такое НОК и НОД двух натуральных чисел

Натуральными числами называют числа, которые используются при счете – 1, 2, 3, 16, 25, 101, 2560 и далее до бесконечности. Ноль, отрицательные и дробные или нецелые числа не относятся к натуральным.

Наименьшее общее кратное (НОК) двух натуральных чисел a и b – это наименьшее число, которое делится без остатка на каждое из рассматриваемых чисел.

Наибольший общий делитель (НОД) двух натуральных чисел a и b – это наибольшее число, на которое делится без остатка каждое рассматриваемое число.

Свойства НОК и НОД для натуральных чисел a и b

(НОД (a, b) = НОД (b, a);)
(НОК (a, b) = НОК (b, a);)
(НОК;(a,b)=frac<НОД;(a,b)>.)

Особенности вычисления, алгоритм Евклида

Рассмотрим два способа определения НОД и НОК с помощью алгоритма Евклида:

Способ деления.

При делении целых чисел с остатком, где a — делимое, b – делитель (b не равно 0) находят целые числа q и r согласно равенству (a=btimes) q+r, в котором q – неполное частное, r – остаток при делении (не отрицательное, по модулю меньше делителя).

Чтобы вычислить НОД, первоначально нужно выбрать наибольшее из двух чисел и поделить его на меньшее. Пока остаток не станет равным нулю, повторяется цикл деления делителя на остаток от деления в соответствии с формулой.

Вычислим НОД для чисел 12 и 20. Делим 20 на 12 и получаем 1 и 8 в остатке. Запишем иначе:

(20=12times1+8) , так как остаток не равняется нулю, продолжаем деление. Делим 12 на 8 и получаем 1 и 4 в остатке. Записываем: (12=8times1+4) и по аналогии делим 8 на 4 и получаем 2 и 0 в остатке. НОД равен остатку, предшествующему нулю.

НОД (12;20) = 4

НОК получаем согласно свойству (НОК (a, b) = НОК;(a,b)=frac<НОД;(a,b)>.) Подставляем числовые значения:

НОК (12; 20) = (12times20div4=60)

НОК (12;20) = 60

Способ вычитания.

Здесь повторяется цикл вычитания из наибольшего числа меньшего числа до момента, пока разность не станет равна нулю. НОД равен предшествующей нулю разности.

Вычислим НОД для тех же чисел, 12 и 20.

20 – 12 = 8 (разность не равна нулю, продолжаем)

НОД (12;20) = 4

НОК находим также, как и при методе деления.

Правило нахождения наибольшего общего делителя (НОД)

Для нахождения наибольшего общего делителя воспользуемся пошаговым алгоритмом:

Разложить числа на простые множители.
Найти общий множитель одного и другого числа.
Перемножить общие множители, если их несколько, и их произведение будет НОД.

Возьмем натуральные числа 24 и 36.

Правильно записать следующим образом:

В случае, когда одно или оба числа относятся к простым, т.е. делятся только на единицу и на само себя, то их НОД равняется 1.

Правило нахождения наименьшего общего кратного (НОК)

Для нахождения наименьшего общего кратного воспользуемся подробным алгоритмом:

Наибольшее из чисел, а затем остальные разложить на простые множители.
Выделить те множители, которые отсутствуют у наибольшего.
Перемножить множители п. 2 и множители наибольшего числа, получить НОК.

Возьмем натуральные числа 9 и 12.

(9=3times3) (видим, что у числа 12 отсутствует одна тройка)

Эта статья появилась на свет совершенно неожиданно. Мне на глаза случайно попался код вычисления НОД на C#.

С первого взгляда мне даже всё понравилось: простенько, лаконичненько и без лишнего выпендрёжа. Однако чем дольше я рассматривал этот код, тем больше возникало сомнений в его эффективности. Я решил сделать маленькое исследование.

В адаптации на C++ код выглядел примерно так:

Подготовка

перейти от типа int к типу long , что бы иметь больший простор для маневра;
оформить вычисление НОД в виде функции;
в функции main вызывать альтернативные версии функции вычисления НОД и сравнивать их производительность.

Очевидный прототип функции: long gcd(long a, long b) . Имя функции от англ. Greatest Common Divisor – т.е. НОД.

Для такой несложной задачи я не стал связываться с профилировщиком, а использовал примитивный тайминг (подробности можно посмотреть в статье «Оптимизация кода через ручной тайминг»).

Окончательный вариант «испытательного стенда» приведён в конце статьи. А в процессе исследований я пользовался его упрощённым вариантом, обеспечивавшим запуск одной из испытуемых функций и таймирование.

В коде я не пользоваться библиотечными функциями, что бы максимальный объём кода был контролируемым. Использование библиотечных функций типа min или swap — отдельная тема для экспериментов. Оставляю её для особо дотошных читателей.

01 перебор от произвольного числа

Этот алгоритм – стартовая точка исследования. Идея алгоритма очень проста: гоним переменную цикла от первого числа до 1. Если оба числа делятся на переменную цикла без остатка, значит переменная цикла и равна НОД; цикл можно завершить досрочно. Если цикл прошёл до конца, значит для этих чисел НОД равен 1.

Очевидный недостаток – несимметричность относительно аргументов. Очевидно, что НОД меньше или равен меньшему из двух чисел. Поэтому гнать цикл от большего числа не имеет смысла.

02 перебор от минимального числа

Просто добавляем простейшую функцию для вычисления минимального числа для пары чисел и инициализируем переменную цикла меньшим из двух чисел. В половине случаев такая оптимизация работать не будет (когда первый аргумент и так меньше второго); зато в другой половине случаев выигрыш по времени может быть весьма значительным.

03 алгоритм с разложением на делители

Но второй вариант так и остался алгоритмом с последовательным перебором. Что можно попробовать ещё?

Из школьного курса математики известно, что НОД можно найти из разложения чисел на простые множители.

НОД будет равен произведению простых множителей, общих для обоих чисел. Например:

Реализуем эту идею:

Первый if отлавливает ситуацию, когда оба числа делятся нацело на переменную цикла и, следовательно, переменная цикла является общим простым (!) множителем для обоих чисел и учитывается для вычисления НОД. Остальные два if отлавливают случаи, когда только одно из чисел делится на переменную цикла; эти множители в НОД не входят.

По-хорошему, цикл for должен перебирать только простые числа. Но нахождение простых чисел является самостоятельной вычислительной задачей, которую здесь решать не хотелось бы. Можно, конечно, использовать таблицу простых чисел, например, в пределах первой тысячи, а для больших чисел, в случае необходимости, вычислять простые числа проверкой на простоту. Но я не стал забираться в дебри факторизации натуральных чисел, а просто закрыл глаза на заведомо холостые проходы цикла for , когда переменная цикла не является простым числом, поскольку после нахождения любого из множителей хотя бы для одного из чисел цикл стартует заново.

Третий вариант по производительности не плох. Но пока это самопал. А что придумали умные люди за многовековую историю математики? «O’key, Гуг. то есть, Википедия, что такое НОД?» Вот, кстати, описано нахождение НОД через каноническое разложение на простые множители, которое мы уже реализовали. А вот что-то новенькое.

04 алгоритм Евклида (рекурсивный)

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.

Реализуем рекурсивную версию:

Считается, что рекурсивные алгоритмы менее эффективны, чем итерационные, за счёт накладных расходов на вызов функции. Для проверки делаем и итерационный вариант.

05 алгоритм Евклида (итерационный)

Кстати, в Викиучебнике есть и другие реализации алгоритма Евклида.

06 бинарный алгоритм (рекурсивный)

НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;

НОД(1, n) = 1; НОД(m, 1) = 1;

Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);

Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);

Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);

Если m, n нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);

Если m, n нечётные и n REPEAT_TIMES раз. Время работы функции записывается в элемент массива, соответствующий этой функции. После того, как все тесты пройдены, результаты из массива делятся на количество наборов данных – получаем среднее время для набора.

Тестирование

Программа компилировалась под MS Visual Studio 2013 и TDM-GCC 4.8.1 в режиме 64-bit Release.

Как и ожидалось, первый алгоритм катастрофически неэффективен. Алгоритм №2 – минимальный костыль для №1 – работает почти в 2 раз быстрее.

Третий алгоритм неожиданно показал очень достойный результат: в 50 раз быстрее алгоритма №2.

Четвёртый и пятый варианты – алгоритм Евклида: рекурсивная версия, как ни странно, обогнала итерационную. По сравнению с третьим вариантом время улучшилось почти на порядок.

Бинарный алгоритм Евклида показал наилучшие результаты. Из трёх вариантов реализации рекурсивная версия – самая неторопливая. Наилучший результат у оптимизированной версии с использованием битовых операций.

Итого, самая производительная версия работает более чем в 2500 раз быстрее, чем изначальный вариант.

Примечание. Время, указанное в таблице – это время выполнения REPEAT_TIMES вызовов функции.

Выводы

Выводы достаточно банальны, но всё же:

Первый пришедший на ум алгоритм решения какой-то задачи часто неоптимален. Хотя и может правильно и достаточно приемлемо работать в определённых условиях.
Всегда надо попробовать подумать над усовершенствованием алгоритма или над альтернативным вариантом.
Учите математику!
Если есть возможность, посмотрите что сделали люди до вас. Может не стоит изобретать велосипед?
Оптимизируйте код.

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

Калькулятор для нахождения НОД и НОК

Найдено НОД и НОК:

Как пользоваться калькулятором

Введите числа в поле для ввода
В случае ввода некорректных символов поле для ввода будет подсвечено красным
нажмите кнопку «Найти НОД и НОК»

Как вводить числа

Числа вводятся через пробел, точку или запятую
Длина вводимых чисел не ограничена, так что найти НОД и НОК длинных чисел не составит никакого труда

Что такое НОД и НОК?

Наибольший общий делитель нескольких чисел – это наибольшее натуральное целое число, на которое все исходные числа делятся без остатка. Наибольший общий делитель сокращённо записывается как НОД.
Наименьшее общее кратное нескольких чисел – это наименьшее число, которое делится на каждое из исходных чисел без остатка. Наименьшее общее кратное сокращённо записывается как НОК.

Как проверить, что число делится на другое число без остатка?

Чтобы узнать, делится ли одно число на другое без остатка, можно воспользоваться некоторыми свойствами делимости чисел. Тогда, комбинируя их, можно проверять делимость на некоторые их них и их комбинации.

Некоторые признаки делимости чисел

1. Признак делимости числа на 2
Чтобы определить, делится ли число на два (является ли оно чётным), достаточно посмотреть на последнююю цифру этого числа: если она равна 0, 2, 4, 6 или 8, то число чётно, а значит делится на 2.
Пример: определить, делится ли на 2 число 34938 .
Решение: смотрим на последнюю цифру: 8 — значит число делится на два.

2. Признак делимости числа на 3
Число делится на 3 тогда, когда сумма его цифр делится на три. Таким образом, чтобы определить, делится ли число на 3, нужно посчитать сумму цифр и проверить, делится ли она на 3. Даже если сумма цифр получилась очень большой, можно повторить этот же процесс вновь.
Пример: определить, делится ли число 34938 на 3.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 3, а значит и число делится на три.

3. Признак делимости числа на 5
Число делится на 5 тогда, когда его последняя цифра равна нулю или пяти.
Пример: определить, делится ли число 34938 на 5.
Решение: смотрим на последнюю цифру: 8 — значит число НЕ делится на пять.

4. Признак делимости числа на 9
Этот признак очень похож на признак делимости на тройку: число делится на 9 тогда, когда сумма его цифр делится на 9.
Пример: определить, делится ли число 34938 на 9.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 9, а значит и число делится на девять.

Как найти НОД и НОК двух чисел

Как найти НОД двух чисел

Наиболее простым способом вычисления наибольшего общего делителя двух чисел является поиск всех возможных делителей этих чисел и выбор наибольшего из них.

Рассмотрим этот способ на примере нахождения НОД(28, 36) :

Раскладываем оба числа на множители: 28 = 1·2·2·7 , 36 = 1·2·2·3·3
Находим общие множители, то есть те, которые есть у обоих чисел: 1, 2 и 2.
Вычисляем произведение этих множителей: 1·2·2 = 4 — это и есть наибольший общий делитель чисел 28 и 36.

Как найти НОК двух чисел

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

Для вычисления НОК нужно вычислить произведение исходных чисел и затем разделить его на предварительно найденный НОД. Найдём НОК для тех же чисел 28 и 36:

Находим произведение чисел 28 и 36: 28·36 = 1008
НОД(28, 36), как уже известно, равен 4
НОК(28, 36) = 1008 / 4 = 252 .

Нахождение НОД и НОК для нескольких чисел

Наибольший общий делитель можно находить и для нескольких чисел, а не только для двух. Для этого числа, подлежащие поиску наибольшего общего делителя, раскладывают на простые множители, затем находят произведение общих простых множителей этих чисел. Также для нахождение НОД нескольких чисел можно воспользоваться следующим соотношением: НОД(a, b, c) = НОД(НОД(a, b), c).

Аналогичное соотношение действует и для наименьшего общего кратного чисел: НОК(a, b, c) = НОК(НОК(a, b), c)

Пример: найти НОД и НОК для чисел 12, 32 и 36.

Cперва разложим числа на множители: 12 = 1·2·2·3 , 32 = 1·2·2·2·2·2 , 36 = 1·2·2·3·3 .
Найдём обшие множители: 1, 2 и 2 .
Их произведение даст НОД: 1·2·2 = 4
Найдём теперь НОК: для этого найдём сначала НОК(12, 32): 12·32 / 4 = 96 .
Чтобы найти НОК всех трёх чисел, нужно найти НОД(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , НОД = 1·2·2·3 = 12 .
НОК(12, 32, 36) = 96·36 / 12 = 288 .

А Вы знаете, что мы пишем программы на C, C++, C#, Pascal и Python?

Так что если Вам нужно написать программу на C/C++, C#, Pascal или Python — мы с радостью поможем с этим!

В том числе мы занимаемся репетиторством по информатике и программированию, а также готовим к ОГЭ и ЕГЭ!

Почему именно мы?

Более 1800 выполненных заказов;
Более 170 отзывов;
Качественное решение
Короткие сроки и привлекательные цены
Различные акции и скидки

Как с нами связаться?

группа Вконтакте: vk.com/programforyou
наша почта: [email protected]

Programforyou — доверяя нам писать программы, вы получаете качественное решение в короткие сроки по привлекательной цене!

Содержание статьи

Как найти наибольший общий делитель чисел
Как найти количество делителей
Как найти наименьшее общее кратное чисел

Нахождение наибольшего общего делителя: основные термины

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

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

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

Все натуральные числа можно разделить на себя и единицу, однако единственным четным простым числом является 2, все остальные можно поделить на двойку. Поэтому простыми могут быть только нечетные числа.

Простых чисел достаточно много, полного списка их не существует. Для нахождения НОД удобно использовать специальные таблицы с такими числами.

Большинство натуральных чисел могут делиться не только на единицу, самих себя, но и на другие числа. Так, например, число 15 можно поделить еще на 3 и 5. Все их называют делителями числа 15.

Таким образом, делитель любого натурального числа А — это число, на которое оно может быть разделено без остатка. Если у числа имеется более двух натуральных делителей, его называют составным.

У числа 30 можно выделить такие делители, как 1, 3, 5, 6, 15, 30.

Можно заметить, что 15 и 30 имеют одинаковые делители 1, 3, 5, 15. Наибольший общий делитель этих двух чисел — 15.

Таким образом, общим делителем чисел А и Б называется такое число, на которое можно поделить их нацело. Наибольшим можно считать максимальное общее число, на которое можно их разделить.

Для решения задач используется такая сокращенная надпись:

Например, НОД (15; 30) = 30.

Чтобы записать все делители натурального числа, применяется запись:

В данном примере у натуральных чисел имеется только один общий делитель. Их называют взаимно простыми, соответственно единица и является их наибольшим общим делителем.

Как найти наибольший общий делитель чисел

Чтобы найти НОД нескольких чисел, нужно:

— найти все делители каждого натурального числа по отдельности, то есть разложить их на множители (простые числа);

— выделить все одинаковые множители у данных чисел;

— перемножить их между собой.

Например, чтобы вычислить наибольший общий делитель чисел 30 и 56, нужно записать следующее:

Чтобы не путаться при разложении, удобно записывать множители при помощи вертикальных столбиков. В левой части от черты нужно разместить делимое, а в правой — делитель. Под делимым следует указать получившееся частное.

Так, в правом столбце окажутся все нужные для решения множители.

Одинаковые делители (найденные множители) можно для удобства подчеркнуть. Их следует переписать и перемножить и записать наибольший общий делитель.

НОД (30; 56) = 2 * 5 = 10

Вот так просто на самом деле найти наибольший общий делитель чисел. Если немного потренироваться, делать это можно будет практически на автомате.