Нахождение наибольшего общего делителя

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

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

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

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

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

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.

Смотрите также: