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

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

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

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

Решение задачи на языке программирования Python

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

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 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 ) : . Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.

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

1. Из большего числа вычитаем меньшее.
2. Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
4. Переходим к пункту 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

X Скрыть Наверх

Решение задач на Python

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

Ал­го­ритм Ев­кли­да — эф­фек­тив­ный ме­тод вы­чис­ле­ния наи­боль­ше­го об­ще­го де­ли­те­ля (НОД). На­зван в честь гре­че­ско­го ма­те­ма­ти­ка Ев­кли­да. Из­ло­жим схе­му ал­го­рит­ма в тек­сто­вом ви­де:

1. Боль­шее чис­ло де­лим на мень­шее;
2. Ес­ли де­лит­ся без остат­ка, то мень­шее чис­ло и есть НОД. За­вер­ша­ем про­грам­му и вы­во­дим ре­зуль­тат;
3. Ес­ли есть оста­ток, то боль­шее за­ме­ня­ем на оста­ток от де­ле­ния;
4. Пе­ре­хо­дим к пунк­ту 1;

Код про­грам­мы мож­но ре­дак­ти­ро­вать. Вы мо­же­те впи­сать свои чис­ла а и b .

a = 50 b = 130 while a!=0 and b!=0: if a > b: a = a % b else: b = b % a print (a+b)

Ал­го­ритм от­но­сит­ся к чис­лу клас­си­че­ских.

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

Всем привет! Занимаюсь изучением языка Python. Никак не могу решить задачу с академии яндекса по нахождению НОДа нескольких чисел :(. Задача из раздела «Вложенные Циклы». Суть заключается в следующем: «В одном из местных НИИ часто требуется находить наибольший общий делитель (НОД) нескольких чисел. Вам уже доверяют, так что вновь пришли с этой задачей. Формат ввода В первой строке записано одно число NN — количество данных. В каждой из последующих NN строк записано по одному натуральному числу. Формат вывода Требуется вывести одно натуральное число — НОД всех данных чисел (кроме NN)» Но, решить надо, как я понял, без использования списков, словарей, готовых функций (типа math.gcd()) и т.д., т.к. тема вложенные циклы идет после тем: Ввод и вывод данных. Операции с числами, строками. Форматирование Условный оператор Циклы. Т.е. предполагается, что я владею только перечисленными выше темами. Даже не знаю с какой стороны подойти. Конечно, можно использовать уже готовую функцию math.gcd(), но очень хочется понять алгоритм решения. Спасибо всем откликнувшимся ☻

Отслеживать
задан 12 фев в 16:40
21 3 3 бронзовых знака
12 фев в 16:41
12 фев в 16:48
@Nowhere Man Первый линк — неудачные ответы
12 фев в 16:57

но очень хочется понять алгоритм решения — Неужели он нигде не описан, и здесь на сайте нет реализаций?

12 фев в 17:07

Есть реализация только для 2х чисел, либо с использованием уже готовой функции math.gcd(). Другого я не нашел.

Найти наибольший общий делитель двух чисел. Python

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

Не нужно беспокоиться о правильной формуле или о том, как её применять. Нейросеть пишет текст самостоятельно и быстро. Без лишних затрат времени и усилий ты получишь ответ, который требуется. Просто загрузи числа и нажми на кнопку «решить». Довольно просто, не правда ли?

Не откладывай на потом решение задачи, воспользуйся нейросетью онлайн и экономь своё время и нервы. Будь профессионалом в решении задач — стань пользователем нашей нейросети!