НОД чисел онлайн
Наибольшим общим делителем нескольких натуральных чисел называется наибольшее натуральное число на которое делятся эти числа без остатка
Выберите количество чисел для нахождения НОД
2 числа3 числа4 числа5 чисел6 чисел
Введите числа
Нахождение НОД с помощью разложения на простые множители
1) Для начала нужно каждое число разложить на простые множители
2) Потом подчеркнуть общие множители
3) Перемножить все общие множители
4) Результатом умножения общих множителей будет НОД
Разберём пример
Найдём НОД(8,16)
Разложим числа
8 = 2 × 2 × 2
16 = 2 × 2 × 2 × 2
Подчеркнём общие множители
8 = 2 × 2 × 2
16 = 2 × 2 × 2 × 2
Перемножим общие множители
НОД(8, 16) = 2 × 2 × 2 = 8
Нод 3 чисел и более
Всё по аналогии с 2 числами
Разберём пример
Найдём НОД(8,16,32)
Разложим числа
8 = 2 × 2 × 2
16 = 2 × 2 × 2 × 2
32 = 2 × 2 × 2 × 2 × 2
Подчеркнём общие множители
8 = 2 × 2 × 2
16 = 2 × 2 × 2 × 2
32 = 2 × 2 × 2 × 2 × 2
Перемножим общие множители
НОД(8, 16, 32) = 2 × 2 × 2 = 8
Что может калькулятор ?
Находить НОД 2 чисел
Находить НОД 3 чисел
Находить НОД 4 чисел
Находить НОД 5 чисел
Находить НОД 6 чисел
Отображает алгоритм нахождения НОД
Похожие калькуляторы
Нахождение НОД и НОК чисел
Онлайн-калькулятор “Нахождение НОД и НОК чисел“. Наш калькулятор поможет вам найти наибольший общий делить (НОД) и наименьшее общее кратное (НОК) чисел. Особенностью данного калькулятора является то, что он может находить НОК и НОД не только двух чисел, но и трех или четырех чисел. Введите натуральные числа и нажмите кнопку “Вычислить” и наш калькулятор не просто выдаст ответ, но и представит подробное решение, где последовательно будет изложен порядок нахождения НОД и НОК чисел.
Выберите количество чисел, для которых требуется найти НОД и НОК:
2 числа
3 числа
4 числа
| Первое число | Второе число |
Наибольший общий делитель нескольких чисел – это наибольшее натуральное целое число, на которое эти числа делятся без остатка. Наибольший общий делитель обозначается следующим образом: НОД (18; 48) = 6
Наименьшее общее кратно нескольких чисел – это самое меньшее число, которое делится на каждое из этих чисел без остатка. Например: НОК (18; 48) = 144
Это следует знать!
Как определить, что число делится на 3 без остатка? Очень просто – на 3 делятся только те числа, сумма цифр которых делится на 3. Например: число 795 делится на 3, так как сумма его цифр 7 + 9 + 5 = 21 делится на 3.
21 : 3 = 7
Алгоритм Евклида – нахождение наибольшего общего делителя
Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.
Решение задачи на языке программирования Python
Алгоритм нахождения НОД делением
- Большее число делим на меньшее.
- Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
- Если есть остаток, то большее число заменяем на остаток от деления.
- Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6
a = int(input()) b = int(input()) while a != 0 and b != 0: if a > b: a = a % b else: b = b % a print(a + b)
В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для определения НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.
Если условием завершения цикла является равенство хотя бы одной из переменных нулю (a == 0 or b == 0), то условием продолжения его работы является обратное этому условие – обе переменные должны иметь отличные от нуля значения (a != 0 and b != 0).
Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs(a) > abs(b):. Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.
Алгоритм нахождения НОД вычитанием
- Из большего числа вычитаем меньшее.
- Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
- Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
- Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 – 18 = 12
18 – 12 = 6
12 – 6 = 6
6 – 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6
a = int(input()) b = int(input()) while a != b: if a > b: a = a - b else: b = b - a print(a)
Функция, вычисляющая НОД
def gcd(m, n): while m != n: if m > n: m = m - n else: n = n - m return n a = int(input()) b = int(input()) print(gcd(a, b))
Функция gcd модуля math
В модуле math языка программирования Python есть функция gcd, вычисляющая наибольший общий делитель двух чисел.
>>> import math >>> math.gcd(30, 18) 6
Больше задач в PDF
Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.
Как найти НОД?
Способов найти НОД несколько. Мы рассмотрим один из часто используемых в математике — это нахождение НОД при помощи разложения чисел на простые множители. В общем случае алгоритм будет выглядеть следующим образом:
- разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);
- выбрать одинаковые множители, входящие в оба разложения;
- найти их произведение.
Примеры нахождения наибольшего общего делителя
Рассмотрим приведенный алгоритм на конкретных примерах:
Пример 1: найти НОД 12 и 8
1. Раскладываем 12 и 8 на простые множители:
2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 2 и 2
3. Перемножаем эти множители и получаем: 2 · 2 = 4
Ответ: НОД (8; 12) = 2 · 2 = 4.
Пример 2: найти НОД 75 и 150
Этот пример, как и предыдущий с легкостью можно высчитать в уме и вывести ответ 75, но для лучшего понимания работы алгоритма, проделаем все шаги:
1. Раскладываем 75 и 150 на простые множители:
2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5
3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75
Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.
Частный случай или взаимно простые числа
Нередко встречаются ситуации, когда оба числа взаимно простые, т.е. общий делитель равен единице. В этом случае, алгоритм будет выглядеть следующим образом:
Пример 3: найти НОД 9 и 5
1. Раскладываем 5 и 9 на простые множители:
Видим, что одинаковых множителей нет, а значит, что это частный случай (взаимно простые числа). Общий делитель — единица.
Как найти НОД
- Нахождение путём разложения на множители
- Алгоритм Евклида
Рассмотрим два способа нахождения наибольшего общего делителя.
Нахождение путём разложения на множители
Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.
Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.
Пример 1. Найти НОД (84, 90).
Решение: Раскладываем числа 84 и 90 на простые множители:
Итак, мы подчеркнули все общие простые множители, осталось перемножить их между собой:
2 · 3 = 6.
Таким образом, НОД (84, 90) = 6.
Пример 2. Найти НОД (15, 28).
Решение: Раскладываем 15 и 28 на простые множители:
Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель — единица.
НОД (15, 28) = 1.
Алгоритм Евклида
Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.
Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.
Если большее из двух данных чисел делится на меньшее, то число, которое меньше и будет их наибольшим общим делителем.
Пример 1. Возьмём два числа 27 и 9. Так как 27 делится на 9 и 9 делится на 9, значит, 9 является общим делителем чисел 27 и 9. Этот делитель является в тоже время и наибольшим, потому что 9 не может делиться ни на какое число, большее 9. Следовательно:
НОД (27, 9) = 9.
В остальных случаях, чтобы найти наибольший общий делитель двух чисел используется следующий порядок действий:
- Из двух данных чисел большее число делят на меньшее.
- Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
- Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
- Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
- Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.
Пример 2. Найдём наибольший общий делитель чисел 140 и 96:
1) 140 : 96 = 1 (остаток 44)
2) 96 : 44 = 2 (остаток 8)
3) 44 : 8 = 5 (остаток 4)
4) 8 : 4 = 2
Последний делитель равен 4 — это значит:
НОД (140, 96) = 4.
Последовательное деление так же можно записывать столбиком:
Чтобы найти наибольший общий делитель трёх и более данных чисел, используем следующий порядок действий:
- Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
- Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
- Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.
Пример 3. Найдём наибольший общий делитель чисел 140, 96 и 48. НОД чисел 140 и 96 мы уже нашли в предыдущем примере (это число 4). Осталось найти наибольший общий делитель числа 4 и третьего данного числа — 48:
48 : 4 = 12
48 делится на 4 без остатка. Таким образом:
НОД (140, 96, 48) = 4.
