Наибольший общий делитель (НОД) двух целых чисел
Этот калькулятор находит наибольший общий делитель (НОД) двух целых чисел алгоритмом Евклида.
Наибольший общий делитель (НОД) двух целых чисел
Первое число
Второе число
Рассчитать
Ссылка Сохранить Виджет
Алгоритм Евклида для нахождения НОД
Сейчас я расскажу вам, как находить наибольший общий делитель двух целых чисел алгоритмом Евклида.
Это довольно просто. Надо строить уменьшающуюся последовательность чисел, первое число которой это максимальное из двух целых, чей НОД мы ищем, второе — соответственно, минимальное из двух целых, а каждое следующее представляет из себя остаток от деления пред-предыдущего на предыдущее. Последний ненулевой член последовательности и есть НОД.
Чтобы было легче воспринять, проиллюстрируем это примером. Найдем НОД для чисел 13 и 17.
1 шаг. Сформируем два первых числа последовательности
17, 13
2 шаг. Третье число последовательности — остаток от деления 17 на 13, то есть 4
17, 13, 4
3 шаг. Четвертое число последовательности — остаток от деления 13 на 4, то есть 1
17, 13, 4, 1
4 шаг. Пятое число последовательности — остаток от деления 4 на 1, то есть 0
17, 13, 4, 1, 0
Перед нулем стоит 1 — последний ненулевой член последовательности. Следовательно, это и есть искомый НОД. С учетом того, что и 13 и 17 — простые числа, это действительно так.
Наибольший общий делитель двух чисел
Вычислите наибольший общий делитель чисел A и B согласно алгоритму Евклида
Задание на рекурсивный алгоритме: Вычислите наибольший общий делитель чисел A и B согласно.
Наибольший общий делитель
Написать функцию, которая вычисляет наибольший общий делитель двух целых чисел.
Наибольший общий делитель прямоугольников
Будем говорить, что прямоугольник PP является делителем прямоугольника QQ, если прямоугольник QQ.
Сократить дробь, используя наибольший общий делитель
Даны два натуральных числа a и b, обозначающие соответственно числитель и знаменатель дроби.
Найдите наибольший общий делитель двух натуральных чисел
Найдите наибольший общий делитель двух натуральных чисел. Целые числа могут быть большими, поэтому.
1354 / 651 / 207
Регистрация: 23.03.2014
Сообщений: 3,057
Сообщение было отмечено mik-a-el как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
# ввод целых чисел a = int(input()) b = int(input()) # Пока какое-нибудь из двух числе не будет равно 0, while a != 0 and b != 0: # сравнивать их между собой. # Если первое число больше второго, if a > b: # то находить остаток от деления его на второе число # и присваивать его первой переменной a = a % b # Иначе (когда второе число больше первого) else: # присваивать второй переменной остаток от деления # нацело второго числа на первое b = b % a # Одно из чисел содержит 0, а другое - НОД, но какое - неизвестно. # Проще их сложить, чем писать конструкцию if-else gcd = a + b print(gcd)
Функция НОД
Excel для Microsoft 365 Excel для Microsoft 365 для Mac Excel для Интернета Excel 2021 Excel 2021 для Mac Excel 2019 Excel 2019 для Mac Excel 2016 Excel 2016 для Mac Excel 2013 Excel 2010 Excel 2007 Excel для Mac 2011 Excel Starter 2010 Еще. Меньше
В этой статье описаны синтаксис формулы и использование функции НОД в Microsoft Excel.
Описание
Возвращает наибольший общий делитель двух или более целых чисел. Наибольший общий делитель — это наибольшее целое число, на которое делятся число1 и число2 без остатка.
Синтаксис
Аргументы функции НОД описаны ниже.
- Число1, число2. Число1 является обязательным, последующие числа — нет. От 1 до 255 значений. Если какое-либо из этих чисел не является целым, оно усекается.
Замечания
- Если какой-либо из аргументов не является числом, возвращается #VALUE! значение ошибки #ЗНАЧ!.
- Если какой-либо из аргументов меньше нуля, возвращается значение #NUM! значение ошибки #ЗНАЧ!.
- Единица является делителем любого числа.
- Простое число делится только само на себя и на единицу.
- Если параметр для параметра GCD >=2^53, возвращается #NUM! значение ошибки #ЗНАЧ!.
Пример
Скопируйте образец данных из следующей таблицы и вставьте их в ячейку A1 нового листа Excel. Чтобы отобразить результаты формул, выделите их и нажмите клавишу F2, а затем — клавишу ВВОД. При необходимости измените ширину столбцов, чтобы видеть все данные.
Наибольший общий делитель чисел 5 и 2
Наибольший общий делитель чисел 24 и 36
Наибольший общий делитель чисел 7 и 1
Наибольший общий делитель чисел 5 и 0
Нужна дополнительная помощь?
Нужны дополнительные параметры?
Изучите преимущества подписки, просмотрите учебные курсы, узнайте, как защитить свое устройство и т. д.
В сообществах можно задавать вопросы и отвечать на них, отправлять отзывы и консультироваться с экспертами разных профилей.
Как найти НОД нескольких чисел?
math.gcd Changed in version 3.9: Added support for an arbitrary number of arguments. Formerly, only two arguments were supported.
До версии 3.9, но выше 3.5 можно скомбинировать так:
math.gcd(3, math.gcd(6, 12)) # 3 from math import gcd from functools import reduce reduce(gcd, [3, 12, 6, 18]) # 3 Для версии ниже 3.5:
from functools import reduce def gcd(a, b): return gcd(b, a % b) if b else a reduce(gcd, [3, 6, 12]) # 3