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

Сегодня разберём древний и красивый Алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел, и запрограммируем его на языке C#.

Евклид - древнегреческий учёный, философ, математик, живший в 3 веке до н. э.

Где применяется алгоритм Евклида ?

• Криптографический алгоритм с открытым ключом RSA.
• Является основным инструментом для доказательства теорем в современной теории чисел.

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

Например, для чисел 12 и 8 наибольший общий делитель (НОД) равен 4.

Алгоритм Евклида (метод вычитания)

Основное правило Алгоритма Евклида для метода вычитания:

Т.е. можно заменить большее число - разностью двух чисел, и НОД останется тем же.

Составим алгоритм:

Сначала вводятся числа m, n. Затем входим в цикл. Цикл выполняется пока m и n не равны. Если эти переменные равны, то можно выйти из цикла и распечатать любое число (m или n). Действительно, ведь наибольший общий делитель (НОД) двух одинаковых чисел равен этому числу. В самом цикле заменяем наибольшее число разностью этих чисел, исходя из закономерности описанной выше. Рано или поздно числа станут равными, и это значение и будет НОД.

Запрограммируем Алгоритм Евклида на языке C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp38
{
    class Program
    {
        static void Main(string[] args)
        {
            int m, n, nod;
            m = Convert.ToInt32(Console.ReadLine());
            n = Convert.ToInt32(Console.ReadLine());

            while(m != n)
            {
                if(m > n)
                {
                    m = m - n;
                }
                else
                {
                    n = n - m;
                }
            }

            nod = n;
            Console.WriteLine("НОД: " + nod);

            Console.ReadKey();
        }
    }
}

Алгоритм Евклида (метод деления)

Можно алгоритм Евклида написать и через остаток от деления!

Где символ % - это остаток от деления.

Запрограммируем метод деления Алгоритма Евклида на C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp38
{
    class Program
    {
        static void Main(string[] args)
        {
            int m, n, nod;
            m = Convert.ToInt32(Console.ReadLine());
            n = Convert.ToInt32(Console.ReadLine());

            while(m!= 0 && n!=0)
            {
                if(m > n)
                {
                    m = m % n;
                }
                else
                {
                    n = n % m;
                }
            }

            nod = m + n;
            Console.WriteLine("НОД: " + nod);

            Console.ReadKey();
        }
    }
}

На этом всё, удачи!