Поиск наибольшего общего делителя в Python

• 17.01.2024
• 283
• Основы Python
• Числа

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

Методы нахождения НОД в Python

Использование встроенной функции math.gcd()

Самый простой и эффективный способ найти НОД в Python – использовать встроенную функцию gcd() из модуля math.

import math

num1 = 28
num2 = 35

print("Наибольший общий делитель:", math.gcd(num1, num2))

# Наибольший общий делитель: 7

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

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

num1 = 28
num2 = 35

print("Наибольший общий делитель:", gcd(num1, num2))

# Наибольший общий делитель: 7

Примеры

Рассмотрим несколько примеров использования этих методов.

Пример 1: Простые числа

num1 = 17
num2 = 31

print("math.gcd:", math.gcd(num1, num2))  # Вывод: 1
print("gcd функция:", gcd(num1, num2))    # Вывод: 1

Так как 17 и 31 – простые числа и не имеют общих делителей, кроме 1, оба метода возвращают 1.

Пример 2: Составные числа

num1 = 48
num2 = 60

print("math.gcd:", math.gcd(num1, num2))  # Вывод: 12
print("gcd функция:", gcd(num1, num2))    # Вывод: 12

Здесь числа 48 и 60 имеют общие делители, и наибольший из них – 12.

Заключение

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