Как найти наибольший общий делитель программирование

Алгоритм Евклида (или алгоритм Евклида) — это метод эффективного нахождения наибольшего общего делителя (НОД) двух чисел. НОД двух целых чисел, X а также Y, является наибольшим числом, которое делит оба X а также Y не оставляя остатка.

Например,

Потренируйтесь в этой проблеме

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

Например, 21 — это НОД 252 и 105 (252 = 21 × 12 а также 105 = 21 × 5), а то же число 21 также является НОД 105 и 147 (147 = 252 - 105).

 
Поскольку эта замена уменьшает большее из двух чисел, повторение этого процесса дает последовательно меньшие пары чисел, пока два числа не станут равными. Когда это происходит, они являются GCD исходных двух чисел.

Следующая программа на C демонстрирует это:

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

 
Более эффективная версия алгоритма заменяет большее из двух чисел его остатком при делении на меньшее. Алгоритм останавливается при достижении нулевого остатка, и теперь алгоритм никогда не требует больше шагов, чем пятикратное количество цифр (по основанию 10) меньшего целого числа.

Итеративную и рекурсивную реализацию можно увидеть ниже на C:

Мы можем расширить приведенную выше программу для чтения нескольких входных данных из файла, как показано ниже на C:

 
Также см:

Расширенный алгоритм Евклида — реализация на C, C++, Java и Python

НОД – это математический термин, обозначающий наибольший общий делитель, который может идеально разделить два числа. НОД также известен как наибольший общий фактор(HCF).

Например, HCF / GCD двух чисел 54 и 24 равен 6. Поскольку 6 – это наибольший общий делитель, который полностью делит 54 и 24.

Разберемся как найти НОД двух чисел в Python. 

НОД с использованием функции gcd()

gcd() в python – это встроенная функция, предлагаемая математическим модулем для поиска наибольшего общего делителя двух чисел.

Синтаксис:

 
gcd(a, b) 

Где a и b – два целых числа, которые передаются в качестве аргумента функции gcd().

Давайте создадим программу для печати НОД двух чисел, используя встроенную функцию math.gcd() в python.

math_fun.py

 
# create a program to print the gcd of two number in python using the math.gcd() function. 
import math 
print(" GCD of two number 0 and 0 is ", math.gcd(0, 0)) #math.gcd(a, b), a and b are the two integer number 
print(" GCD of two number 0 and 48 is ", math.gcd(0, 48)) 
a = 60 # assign the number to variable a 
b = 48 # assign the number to variable b 
print(" GCD of two number 60 and 48 is ", math.gcd(a, b)) # pass the variable a and b to math.gcd() function. 
print(" GCD of two number 48 and -12 is ", math.gcd(48, -12)) # pass the integer number 
print(" GCD of two number -24 and -18 is ", math.gcd(-24, -18)) 
print(" GCD of two number -60 and 48 is ", math.gcd(-60, 48)) 

Выход:

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

НОД с использованием рекурсии

Рекурсия – это функция, потребляющая память, определенная в Python, которая вызывает себя через самореферентное выражение. Это означает, что функция будет постоянно вызывать и повторять себя до тех пор, пока не будет выполнено определенное условие для возврата наибольшего общего делителя числа.

Псевдокод алгоритма

Шаг 1: Возьмите два входа, x и y, от пользователя.

Шаг 2: Передайте входной номер в качестве аргумента рекурсивной функции.

Шаг 3: Если второе число равно нулю(0), возвращается первое число.

Шаг 4: В противном случае он рекурсивно вызывает функцию со вторым числом в качестве аргумента, пока не получит остаток, который делит второе число на первое число.

Шаг 5: Вызовите или назначьте gcd_fun() переменной.

Шаг 6: Отобразите НОД двух чисел.

Шаг 7: Выйдите из программы.

Разберемся с программой для нахождения НОД двух чисел с помощью рекурсии.

gcdRecur.py

 
# write a program to understand the GCD of two number in python using the recursion. 
def gcd_fun(x, y): 
    if(y == 0): # it divide every number 
        return x  # return x 
    else: 
        return gcd_fun(y, x % y) 
x =int(input("Enter the first number: ")) # take first no.  
y =int(input("Enter the second number: ")) # take second no.  
num = gcd_fun(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num 

Выход:

Нахождение НОД с помощью цикла

Давайте создадим программу для нахождения НОД двух чисел в Python с помощью циклов.

gcdFile.py

 
def GCD_Loop( a, b): 
    if a > b:  # define the if condition 
        temp = b 
    else: 
        temp = a 
    for i in range(1, temp + 1): 
        if(( a % i == 0) and(b % i == 0 )): 
            gcd = i 
    return gcd 
x = int(input(" Enter the first number: ") ) # take first no.  
y =int(input(" Enter the second number: ")) # take second no.  
num = GCD_Loop(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num 

Выход:

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

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

Алгоритм Евклида – эффективный метод нахождения наибольшего общего делителя двух чисел. Это самый старый алгоритм, который делит большее число на меньшее и берет остаток. Опять же, он делит меньшее число от остатка, и этот алгоритм непрерывно делит число, пока остаток не станет 0.

Например, предположим, что мы хотим вычислить HCF двух чисел, 60 и 48. Затем мы делим 60 на 48; он возвращает остаток 12. Теперь мы снова делим число 24 на 12, а затем он возвращает остаток 0. Таким образом, мы получаем HCF равным 12.

Псевдокод алгоритма Евклида

Шаг 1: Есть два целых числа, например a и b.

Шаг 2: Если a = 0, то НОД(a, b) равен b.

Шаг 3: Если b = 0, НОД(a, b) равен a.

Шаг 4: Найти mod b.

Шаг 5: Предположим, что a = b и b = R.

Шаг 6: Повторяйте шаги 4 и 3, пока mod b не станет равным или большим 0.

Шаг 7: GCD = b и затем распечатайте результат.

Шаг 8: Остановите программу.

Найдем HCF или GCD двух чисел, используя алгоритм Евклида в python.

Euclid.py

 
# Create a program to find the GCD of two number in python using the Euclid's Algorithm. 
def find_hcf(a,b): 
    while(b): 
        a, a = b, a % b 
        return a 
a = int(input(" Enter the first number: ") ) # take first no.  
b = int(input(" Enter the second number: ")) # take second no.  
num = find_hcf(a, b) # call the find_hcf() to get the result 
print("  The HCF of two number a and b is ") 
print(num) # call num 

Выход:

Алгоритм Евклида – это алгоритм для поиска наибольшего общего делителя двух чисел. Алгоритм впервые описан древнегреческим математиком Евклидом.

Наибольший общий делитель (НОД) – это наибольшее число, на которое делятся заданные числа без остатка.

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

Рекурсивная реализация поиска наибольшего общего делителя

Напишем два вспомогательных метода, которые возвращают минимальное и максимальное из двух чисел:

static int Min(int x, int y)
{
    return x < y ? x : y;
}

static int Max(int x, int y)
{
    return x > y ? x : y;
}

Нахождение НОД для двух чисел c использованием вычитания

При каждом рекурсивном вызове вычитаем из максимального числа минимальное, повторяя рекурсивные вызовы до тех пор, пока первый аргумент не будет равен нулю:

static int GCD(int a, int b)
{
    if (a == 0)
    {
        return b;
    }
    else
    {
        var min = Min(a, b);
        var max = Max(a, b);
        //вызываем метод с новыми аргументами
        return GCD(max - min, min);
    }
}

Использование оператора остатка от деления % для вычисления НОД

Для уменьшения количества рекурсивных вызовов, при вычислении, можно воспользоваться оператором остатка от деления и вместо разницы, передавать в метод остаток от деления максимального числа на минимальное.
Чтобы ускорить алгоритм, достаточно изменить знак в строке возврата предыдущего метода с “-” на “%”:

return GCD(max % min, min);

Использование остатка очень ускоряет работу алгоритма поиска НОД. К примеру для пары чисел 1013 и 65 с использованием вычитания метод вызывается 27 раз, а с остатком от деления всего 7.

Вычисление НОД в циклах

Циклическое вычисление наибольшего общего делителя с вычитанием

static int GCD(int a, int b)
{
    if (a == 0)
    {
        return b;
    }
    else
    {
        while (b != 0)
        {
            if (a > b)
            {
                a -= b;
            }
            else
            {
                b -= a;
            }
        }

        return a;
    }
}

Циклический поиск наибольшего общего делителя с остатком от деления

static int GCD(int a, int b)
{
    while (b != 0)
    {
        var temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Программа для поиска НОД чисел

Напишем программу, в которой будем использовать один из методов рассмотренных выше:

using System;

class Program
{
    static int GCD(int a, int b)
    {
        while (b != 0)
        {
            var t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Алгоритм Евклида");
        Console.Write("A = ");
        var a = Convert.ToInt32(Console.ReadLine());
        Console.Write("B = ");
        var b = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine("Наибольший общий делитель чисел {0} и {1} равен {2}", a, b, GCD(a, b));
        Console.ReadLine();
    }
}

Результат работы программы:

Для чисел 36 и 60 программа возвращает значение 12.

Наибольший общий делитель трех чисел

Для получения НОД для трех чисел и более чисел необходимо вызывать метод следующим образом:

var n1 = GCD(GCD(15, 30), 75); //для трех параметров результат 15
var n2 = GCD(GCD(16, 36), GCD(585, 360)); //для четырех чисел результат 1

В первом примере сначала вычисляется НОД(15, 30) = 15, потом результат вычислений передается в качестве аргумента и вычисляется НОД(15, 75) = 15.
Во втором примере вычисляются НОД(16, 36) = 4 и НОД(585, 360) = 45, а результаты передаются в метод НОД(4, 45) = 1.