Знаходження найбільшого спільного дільника

Алгоритм Евкліда – це алгоритм пошуку найбільшого спільного дільника двох чисел. Алгоритм вперше описаний давньогрецьким математиком Евклідом.

Найбільший спільний дільник (НСД) – це найбільше число, на яке діляться без остачі задані числа.

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

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

Напишемо два допоміжні методи, які повертають мінімальне та максимальне з двох чисел:

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

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

Знаходження НСД для двох чисел з використанням віднімання

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

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.

Дивіться також: