Задача: Наибольший общий делитель

Опубликован: 02.11.2024 33

Условие: Напишите программу, которая вычисляет наибольший общий делитель (НОД) для двух целых чисел a и b (включая отрицательные).

Наибольший общий делитель - это наибольшее число, на которое оба числа делятся без остатка.

Решение:

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

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

# функция нахождения НОД вычитанием
def get_gcd(a, b):
    while a != b:
        if abs(a) > abs(b):
            a = abs(a) - abs(b)
        else:
            b = abs(b) - abs(a)
    return a


while True:
    x = int(input("Введите первое число: "))
    y = int(input("Введите второе число: "))
    if x != 0 and y != 0:
        break
    else:
        print("Ошибка. Введите целые числа не равные 0")

print(f"Наибольший общий делитель: {get_gcd(x, y)}")

2. Алгоритм Евклида - нахождения НОД делением.

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

# функция нахождения НОД делением
def get_gcd(a, b):
    while a != 0 and b !=0:
        if abs(a) > abs(b):
            a = abs(a) % abs(b)
        else:
            b = abs(b) % abs(a)
    return a + b

while True:
    x = int(input("Введите первое число: "))
    y = int(input("Введите второе число: "))
    if x != 0 and y != 0:
        break
    else:
        print("Ошибка. Введите целые числа не равные 0")

print(f"Наибольший общий делитель: {get_gcd(x, y)}")

3. Функция gcd() модуля math.

В стандартной библиотеке Python в модуле math есть функция gcd(x, y), вычисляющая наибольший общий делитель двух чисел.

import math

print(f"Наибольший общий делитель: {math.gcd(x, y)}")

4. Нахождение НОД произвольного количества чисел.

Для нахождения НОД трех и более чисел можно воспользоваться функцией reduce() из модуля functools, которая последовательно вычисляет НОД каждой пары смежных чисел из списка.

from math import gcd
from functools import reduce

reduce(gcd, [5, 15, 35, 55])  # 5

Похожие посты

Задача: Решение квадратного уравнения

Задача: Тренажер таблицы умножения

Задача: Наибольший числовой палиндром

Задача: Разложение числа на простые множители

Комментариев нет.