Напишите программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу: НОД(A, B, C) = НОД(НОД(A, B), C). Используйте алгоритм Евклида.

Нужно найти НОД трёх чисел по формуле:

То есть сначала находим НОД двух чисел $A$ и $B$, затем берём результат и находим его НОД с $C$. Для НОД двух чисел используем алгоритм Евклида: пока второе число не стало нулём, заменяем пару $(a,b)$ на $(b, a \bmod b)$. Когда $b=0$, ответ — это $a$.

Ниже пример программы на Python.

Python
def gcd(a, b):
    # Алгоритм Евклида для двух чисел
    a, b = abs(a), abs(b)  # на случай отрицательных чисел
    while b != 0:
        a, b = b, a % b
    return a

def gcd_three(a, b, c):
    # НОД(A, B, C) = НОД(НОД(A, B), C)
    return gcd(gcd(a, b), c)

# Ввод трёх чисел
A, B, C = map(int, input().split())

# Вывод результата
print(gcd_three(A, B, C))

Как это работает:

1. gcd(A, B) вычисляет НОД первых двух чисел по Евклиду.

2. Полученный результат снова передаётся в gcd(…, C), что и даёт НОД трёх чисел согласно формуле.

Пример:

• Ввод: 24 36 18

• НОД(24,36)=12

• НОД(12,18)=6

• Вывод: 6