Нахождение НОД для множества чисел

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

После небольшого гугления нашёл нужный алгоритм. Мою реализацию на C# можно увидеть ниже.

using System;
using System.Linq;

namespace NOD
{
    internal class Program
    {
        private static void Main()
        {
            string str = Console.ReadLine();
            string[] strArray = null;
            long[] array = null;
            if (!String.IsNullOrEmpty(str))
            {
                str = str.Trim();
                strArray = str.Split(' ');
                array = new long[strArray.Length];
            }
            if (strArray != null && strArray.Length > 0)
                for (int i = 0; i < array.Length; i++)
                {
                    array[i] = long.Parse(strArray[i]);
                }

            if (array != null && array.Length > 0)
            {
                #region ArrayNOD

                long nod = array.Min();
                while (true)
                {
                    long temp = nod;
                    foreach (long number in array)
                    {
                        long tDiv = number/nod;
                        if (!(tDiv > 0 && number%nod == 0))
                            nod = number/(tDiv + 1);
                    }
                    if (temp == nod) break;
                }

                #endregion

                Console.WriteLine(nod);
                Console.ReadKey();
            }
            else
            {
                Console.WriteLine("Array is null or empty");
            }
        }
    }
}

Сам алгоритм находится в регионе ArrayNOD

Добавить комментарий