Как найти наибольший общий делитель в c

Алгоритм Евклида для нахождения НОД двух чисел

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

Euclid(30, 50) = 10

Euclid(2740, 1760) = 20

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

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

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

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

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

Наибольший общий делитель

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

В качестве примера рассмотрим значения 320 и 120. НОД этих двух чисел — 40. Если процесс вычитания меньшего числа из большего числа повторяется, со временем одно из значений станет нулевым. В этот момент другое значение будет содержать НОД для исходной пары. Этот итерационный процесс для наших значений примера дает следующие результаты:

Окончательный расчет дает нулевой результат, который оставил бы два значения 40 и ноль. Следовательно, НОД — это значение 40.

Реализация алгоритма Евклида

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

Метод состоит из нескольких этапов. Сначала создается цикл while, который будет продолжать обработку до тех пор, пока одно из значений не будет сведено к нулю. Внутри цикла меньшее из двух значений вычитается из большего. Как только цикл завершился, одно значение будет равно нулю, а другое будет содержать НОД. Возврат НОД осуществляется путем нахождения большего из двух значений.

Примечание: Код в этой статье предполагает, что оба целых числа положительны.

Чтобы создать метод, добавьте следующий код:

Чтобы проверить метод, попробуйте выполнить следующую команду. Это находит НОД 322328 и 122120. Результат должен быть равен 344.

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

Число итераций цикла в предыдущем примере кода может быть огромным. Если одно из двух значений намного больше другого, либо в начале процесса, либо позже, когда значения падают, одно и то же значение может быть вычтено много раз. Мы можем уменьшить число итераций, используя оператор модуля. Применение оператора модуля к двум значениям и замена большего значения результата приводит к одновременному применению нескольких вычитаний. Например, если два значения равны десяти и трем, три будут вычитаться три раза, чтобы уменьшить десять к одному. Используя модуль, мы получаем единицу в единственной итерации, как 10% 3 = 1.

Если результат модуля равен нулю, то найден НОД.

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

В окончательной версии алгоритма Евклида для получения результата используется рекурсия. Это полезно при использовании функциональных языков программирования, таких как F#. Тем не менее, я опишу его здесь, используя C# для полноты картины.

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

Автор этого материала — я — Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML — то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

заметки, си шарп, алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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