Как найти наибольший общий делитель нечетного числа - AvtoShod.ru

Алгоритм Евклида — нахождение наибольшего общего делителя

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

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

Решение задачи на языке программирования 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

Источник

Запомните!

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

Любое натуральное число всегда делится на 1 и на само себя.

Число 2 — наименьшее простое число. Это единственное чётное простое число, остальные простые числа — нечётные.

Простых чисел много, и первое среди них — число 2. Однако нет последнего простого числа. В
разделе «Для учёбы»
вы можете скачать таблицу простых чисел до 997.

Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например:

число 12
делится на 1,
на 2, на 3, на 4,
на 6, на 12;
число 36
делится на 1,
на 2,
на 3,
на 4,
на 6,
на 12,
на 18,
на 36.

Числа, на которые число делится нацело
(для 12 это
1, 2, 3, 4, 6 и 12) называются
делителями числа.

Запомните!

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

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

Обратите внимание, что числа 12 и
36 имеют общие делители.
Это числа: 1, 2, 3, 4, 6, 12.
Наибольший из делителей этих чисел — 12.

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

Запомните!

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

Кратко наибольший общий делитель чисел «a» и «b» записывают так:

НОД (a; b).

Пример: НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример.

Д (7) = {1, 7}

Д (9) = {1, 9}

НОД (7; 9) = 1

Числа
7 и 9 имеют
только один общий делитель — число 1.
Такие числа называют взаимно простыми числами.

Запомните!

Взаимно простые числа — это натуральные числа, которые имеют только
один общий делитель — число 1. Их НОД
равен 1.

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

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

разложить делители чисел на простые множители;

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

Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

Подчёркиваем одинаковые простые множители в обоих числах.

28 = 2 · 2 · 7

64 = 2 · 2 · 2 · 2 · 2 · 2
Находим произведение одинаковых простых множителей и записать ответ;

НОД (28; 64) = 2 · 2 = 4

Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами:
в столбик (как делали выше) или «в строчку».

Первый способ записи НОД

Найти НОД 48 и 36.

НОД (48; 36) = 2 · 2 · 3 = 12

Второй способ записи НОД

Теперь запишем решение поиска НОД в строчку. Найти НОД 10 и 15.

Д (10) = {1, 2, 5, 10}

Д (15) = {1, 3, 5, 15}

Д (10, 15) = {1, 5}

НОД (10; 15) = 5

Ваши комментарии

Важно!

Чтобы оставить комментарий, вам нужно войти на наш сайт при помощи

«ВКонтакте».

Оставить комментарий:

15 ноября 2016 в 17:18

Олеся Ткаченко
(^-^)
Профиль
Благодарили: 0

Сообщений: 1

(^-^)
Олеся Ткаченко
Профиль
Благодарили: 0

Сообщений: 1

Как найти нод чисел

???

0
Спасибо thanks
Ответить

15 ноября 2016 в 21:01
Ответ для Олеся Ткаченко

Антон Ершов
(^-^)
Профиль
Благодарили: 0

Сообщений: 2

(^-^)
Антон Ершов
Профиль
Благодарили: 0

Сообщений: 2

0
Спасибо thanks
Ответить

17 ноября 2016 в 10:07
Ответ для Олеся Ткаченко

Евгений Колосов
(^-^)
Профиль
Благодарили: 12

Сообщений: 197

(^-^)
Евгений Колосов
Профиль
Благодарили: 12

Сообщений: 197

Если интересно, есть урок на эту тему.

0
Спасибо thanks
Ответить

12 октября 2015 в 17:28

Илья Ткачёв
(^-^)
Профиль
Благодарили: 0

Сообщений: 1

(^-^)
Илья Ткачёв
Профиль
Благодарили: 0

Сообщений: 1

НОК чисел 12 6 4 и объяснить как ты это сделал!

0
Спасибо thanks
Ответить

1 июля 2016 в 17:09
Ответ для Илья Ткачёв

Евгений Колосов
(^-^)
Профиль
Благодарили: 12

Сообщений: 197

(^-^)
Евгений Колосов
Профиль
Благодарили: 12

Сообщений: 197

Методика подробно и понятно изложена вот на этой странице http://math-prosto.ru/index.php?page=pages/find_nod_and_nok/find_nod.php

А ответ к твоей задаче можно получить в супер решателе на сайте: http://math-prosto.ru/index.php?page=pages/calculators/find_nok_online.php

И он 12 =) Удачи и учитесь пользоваться поиском =)

0
Спасибо thanks
Ответить

2 октября 2015 в 17:37

Булат Махмудов
(^-^)
Профиль
Благодарили: 0

Сообщений: 1

(^-^)
Булат Махмудов
Профиль
Благодарили: 0

Сообщений: 1

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

0
Спасибо thanks
Ответить

9 июня 2016 в 14:26
Ответ для Булат Махмудов

Евгений Фёдоров
(^-^)
Профиль
Благодарили: 0

Сообщений: 60

(^-^)
Евгений Фёдоров
Профиль
Благодарили: 0

Сообщений: 60

a · b = НОД(a; b) · НОК(a; b)

0
Спасибо thanks
Ответить

21 сентября 2015 в 22:37

Angelina Vorontsovskaya
(^-^)
Профиль
Благодарили: 0

Сообщений: 1

(^-^)
Angelina Vorontsovskaya
Профиль
Благодарили: 0

Сообщений: 1

27=3,3,3. 36=3,3,3.
Наименьшее общее кратное — ?

0
Спасибо thanks
Ответить

22 сентября 2015 в 19:32
Ответ для Angelina Vorontsovskaya

Ольга Морозова
(^-^)
Профиль
Благодарили: 0

Сообщений: 1

(^-^)
Ольга Морозова
Профиль
Благодарили: 0

Сообщений: 1

27=3,3,3
36=2,2,3,3
НОК=3 · 3=9

0
Спасибо thanks
Ответить

6 мая 2015 в 9:20

Сергей Михель
(^-^)
Профиль
Благодарили: 0

Сообщений: 1

(^-^)
Сергей Михель
Профиль
Благодарили: 0

Сообщений: 1

Часиное двух чисел равно наибольшему общему делителю чисел 12 и 16.Сумма этих чисел равна наименьшему общему кратному чисел 50 и 75. Найдите эти числа

0
Спасибо thanks
Ответить

16 апреля 2016 в 8:49
Ответ для Сергей Михель

Евгений Колосов
(^-^)
Профиль
Благодарили: 12

Сообщений: 197

(^-^)
Евгений Колосов
Профиль
Благодарили: 12

Сообщений: 197

Вот тут можно найти объяснение темы НОД и НОК : http://math-prosto.ru/index.php?page=pages/find_nod_and_nok/find_nod.php

А вот тут можно найти математический кальклятор: http://math-prosto.ru/index.php?page=pages/calculators/calculators.php

Решение:
Найдём НОД чисел 12 и 16. Это число 4
Найдём НОК чисел 50 и 75. Это число 150
Обозначим искомые числа как Х и Y и составим уравнения:

x: y=4
x + y=150
x=150-y
150-y: y = 4
y?0
150-y=4y
5y=150
y=30
x=150-30
x=120

Проверка:
120:30=4
4=4
120+30=150
150=150
Ответ: эти числа 120 и 30

0
Спасибо thanks
Ответить

Источник

Загрузить PDF

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

1

Найдите делители чисел. Начните с поиска всех делителей первого и второго числа.
2

Сравните делители обоих чисел и найдите самое большое число, которое есть в списке делителей как первого, так и второго числа. Это число равно НОД.

Реклама

1

Разложите каждое число на простые множители. Простое число — это число, большее 1 и которое делится только на 1 и на само себя. Примеры простых чисел: 5, 17, 97, 331.
2

Найдите общие простые множители. Общий простой множитель может быть только один, или их может быть несколько.
3

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

Изучите пример. Чтобы продемонстрировать этот метод, изучите пример, приведенный на рисунке.

Реклама

Советы

Простое число — это число, которое делится только на 1 и на само себя.
Знаете ли вы, что в третьем веке до н.э. математик Евклид создал алгоритм для вычисления наибольшего общего делителя двух натуральных чисел и двух многочленов?

Об этой статье

Эту страницу просматривали 7409 раз.

Была ли эта статья полезной?

Источник

Как найти НОД

Нахождение путём разложения на множители
Алгоритм Евклида

Рассмотрим два способа нахождения наибольшего общего делителя.

Нахождение путём разложения на множители

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

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

Пример 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 (остаток

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.

Источник

Алгоритм Евклида — нахождение наибольшего общего делителя

Алгоритм нахождения НОД делением

Алгоритм нахождения НОД вычитанием

Функция, вычисляющая НОД

Функция gcd модуля math

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

Первый способ записи НОД

Второй способ записи НОД

Ваши комментарии

Советы

Об этой статье

Была ли эта статья полезной?

Как найти НОД

Нахождение путём разложения на множители

Алгоритм Евклида

Не пропустите также:

Функция `gcd` модуля `math`