Question

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

Answer 1

Ответ:

chislo1 = int(input("Введите число а "))

chislo2 = int(input("Введите число b "))

while chislo1 != 0 and chislo2 != 0:

   if chislo1 > chislo2:

       chislo1 = chislo1 % chislo2

   else:

       chislo2 = chislo2  % chislo1

print(chislo1 + chislo2)

Объяснение:

НОД числа:

берутся два числа. большее число = остаток от деления большего на меньшее. Затем опять большее число (может быть уже второе) = остаток от деления большего на меньшее, и так до тех пор, пока одно из них не станет равно 0. И выводится большее число. В случае если числа равны друг другу, находится остаток от деления второго числа на первое: 0, и выводится первое число. Т.е всё работает.

Answer 2

Конечно! Вот пример программы на Python, которая вычисляет наибольший общий делитель (НОД) двух натуральных чисел с использованием алгоритма Евклида:

pythonCopy code
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Получение входных данных от пользователя
num1 = int(input("Введите первое число: "))
num2 = int(input("Введите второе число: "))

# Вычисление НОД и вывод результата
result = gcd(num1, num2)
print("Наибольший общий делитель:", result)

Эта программа определяет функцию gcd(), которая принимает два аргумента a и b. В цикле она использует алгоритм Евклида для нахождения НОД путем последовательного деления чисел a и b до тех пор, пока b не станет равным 0. Затем функция возвращает a как результат.

Затем программа запрашивает у пользователя два натуральных числа, вызывает функцию gcd() с этими числами и выводит результат.

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