Как найти нод все способы

Нахождение НОД по алгоритму Евклида и с помощью разложения на простые множители.

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

Навигация по странице.

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

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

Напомним суть алгоритма Евклида. Для нахождения наибольшего общего делителя двух чисел a и b ( a и b – целые положительные числа, причем a больше или равно b ) последовательно выполняется деление с остатком, которое дает ряд равенств вида

Деление заканчивается, когда r_k+1=0 , при этом r_k=НОД(a, b) .

Рассмотрим примеры нахождения НОД по алгоритму Евклида.

Найдите наибольший общий делитель чисел 64 и 48 .

Воспользуемся алгоритмом Евклида. В этом примере a=64 , b=48 .

Делим 64 на 48 , получаем 64:48=1 (ост. 16) (при необходимости смотрите правила и примеры деления с остатком), что можно записать в виде равенства 64=48·1+16 , то есть, q₁=1 , r₁=16 .

Теперь делим b на r₁ , то есть, 48 делим на 16 , получаем 48:16=3 , откуда имеем 48=16·3 . Здесь q₂=3 , а r₂=0 , так как 48 делится на 16 без остатка. Мы получили r₂=0 , поэтому это был последний шаг алгоритма Евклида, и r₁=16 является искомым наибольшим общим делителем чисел 64 и 48 .

Покажем решение еще одного примера, но теперь обойдемся без подробных пояснений шагов алгоритма Евклида.

Чему равен НОД чисел 111 и 432 ?

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

Разделив 432 на 111 , получаем равенство 432=111·3+99 .

На следующем шаге делим 111 на 99 , имеем 111=99·1+12 .

Деление 99 на 12 дает равенство 99=12·8+3 .

А 12 на 3 делится без остатка и 12=3·4 . Поэтому это последний шаг алгоритма Евклида, и НОД(432, 111)=3 , следовательно, и искомый наибольший общий делитель чисел 111 и 432 равен 3 .

Для закрепления материала найдем с помощью алгоритма Евклида наибольший общий делитель чисел 661 и 113 .

Найдите НОД(661, 113) по алгоритму Евклида.

Выполняем деление: 661=113·5+96 ; 113=96·1+17 ; 96=17·5+11 ; 17=11·1+6 ; 11=6·1+5 ; 6=5·1+1 , наконец, 5=1·5 . Таким образом, НОД(661, 113)=1 , то есть, 661 и 113 – взаимно простые числа.

Заметим, что если бы мы с самого начала обратились к таблице простых чисел, то выяснили бы, что числа 661 и 113 – простые, откуда можно было бы сразу сказать, что их наибольший общий делитель равен 1 .

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

Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители. Сформулируем правило: НОД двух целых положительных чисел a и b равен произведению всех общих простых множителей, находящихся в разложениях чисел a и b на простые множители.

Приведем пример для пояснения правила нахождения НОД. Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5 . Общими простыми множителями, участвующими в разложении чисел 220 и 600 , являются 2 , 2 и 5 . Следовательно, НОД(220, 600)=2·2·5=20 .

Таким образом, если разложить числа a и b на простые множители и найти произведение всех их общих множителей, то этим будет найден наибольший общий делитель чисел a и b .

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

Найдите наибольший общий делитель чисел 72 и 96 .

Разложим на простые множители числа 72 и 96 :

То есть, 72=2·2·2·3·3 и 96=2·2·2·2·2·3 . Общими простыми множителями являются 2 , 2 , 2 и 3 . Таким образом, НОД(72, 96)=2·2·2·3=24 .

В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что НОД(m·a₁, m·b₁)=m·НОД(a₁, b₁) , где m – любое целое положительное число.

Нахождение НОД трех и большего количества чисел

Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a₁, a₂, …, a_k равен числу d_k , которое находится при последовательном вычислении НОД(a₁, a₂)=d₂ , НОД(d₂, a₃)=d₃ , НОД(d₃, a₄)=d₄ , …, НОД(d_k-1, a_k)=d_k .

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

Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .

Сначала по алгоритму Евклида определим наибольший общий делитель d₂ двух первых чисел 78 и 294 . При делении получаем равенства 294=78·3+60 ; 78=60·1+18 ; 60=18·3+6 и 18=6·3 . Таким образом, d₂=НОД(78, 294)=6 .

Теперь вычислим d₃=НОД(d₂, a₃)=НОД(6, 570) . Опять применим алгоритм Евклида: 570=6·95 , следовательно, d₃=НОД(6, 570)=6 .

Осталось вычислить d₄=НОД(d₃, a₄)=НОД(6, 36) . Так как 36 делится на 6 , то d₄=НОД(6, 36)=6 .

Таким образом, наибольший общий делитель четырех данных чисел равен d₄=6 , то есть, НОД(78, 294, 570, 36)=6 .

НОД(78, 294, 570, 36)=6 .

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

Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.

Разложим числа 78 , 294 , 570 и 36 на простые множители, получаем 78=2·3·13 , 294=2·3·7·7 , 570=2·3·5·19 , 36=2·2·3·3 . Общими простыми множителями всех данных четырех чисел являются числа 2 и 3 . Следовательно, НОД(78, 294, 570, 36)=2·3=6 .

НОД(78, 294, 570, 36)=6 .

Нахождение НОД отрицательных чисел

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

Найдите НОД отрицательных целых чисел −231 и −140 .

Модуль числа −231 равен 231 , а модуль числа −140 равен 140 , и НОД(−231, −140)=НОД(231, 140) . Алгоритм Евклида дает нам следующие равенства: 231=140·1+91 ; 140=91·1+49 ; 91=49·1+42 ; 49=42·1+7 и 42=7·6 . Следовательно, НОД(231, 140)=7 . Тогда искомый наибольший общий делитель отрицательных чисел −231 и −140 равен 7 .

Определите НОД трех чисел −585 , 81 и −189 .

При нахождении наибольшего общего делителя отрицательные числа можно заменить их абсолютными величинами, то есть, НОД(−585, 81, −189)= НОД(585, 81, 189) . Разложения чисел 585 , 81 и 189 на простые множители имеют соответственно вид 585=3·3·5·13 , 81=3·3·3·3 и 189=3·3·3·7 . Общими простыми множителями этих трех чисел являются 3 и 3 . Тогда НОД(585, 81, 189)=3·3=9 , следовательно, НОД(−585, 81, −189)=9 .

Источник

8 способов нахождения наибольшего общего делителя

Эта статья появилась на свет совершенно неожиданно. Мне на глаза случайно попался код вычисления НОД на C#.

С первого взгляда мне даже всё понравилось: простенько, лаконичненько и без лишнего выпендрёжа. Однако чем дольше я рассматривал этот код, тем больше возникало сомнений в его эффективности. Я решил сделать маленькое исследование.

В адаптации на C++ код выглядел примерно так:

Подготовка

1. перейти от типа int к типу long , что бы иметь больший простор для маневра;
2. оформить вычисление НОД в виде функции;
3. в функции main вызывать альтернативные версии функции вычисления НОД и сравнивать их производительность.

Очевидный прототип функции: long gcd(long a, long b) . Имя функции от англ. Greatest Common Divisor – т.е. НОД.

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

Окончательный вариант «испытательного стенда» приведён в конце статьи. А в процессе исследований я пользовался его упрощённым вариантом, обеспечивавшим запуск одной из испытуемых функций и таймирование.

В коде я не пользоваться библиотечными функциями, что бы максимальный объём кода был контролируемым. Использование библиотечных функций типа min или swap — отдельная тема для экспериментов. Оставляю её для особо дотошных читателей.

01 перебор от произвольного числа

Этот алгоритм – стартовая точка исследования. Идея алгоритма очень проста: гоним переменную цикла от первого числа до 1. Если оба числа делятся на переменную цикла без остатка, значит переменная цикла и равна НОД; цикл можно завершить досрочно. Если цикл прошёл до конца, значит для этих чисел НОД равен 1.

Очевидный недостаток – несимметричность относительно аргументов. Очевидно, что НОД меньше или равен меньшему из двух чисел. Поэтому гнать цикл от большего числа не имеет смысла.

02 перебор от минимального числа

Просто добавляем простейшую функцию для вычисления минимального числа для пары чисел и инициализируем переменную цикла меньшим из двух чисел. В половине случаев такая оптимизация работать не будет (когда первый аргумент и так меньше второго); зато в другой половине случаев выигрыш по времени может быть весьма значительным.

03 алгоритм с разложением на делители

Но второй вариант так и остался алгоритмом с последовательным перебором. Что можно попробовать ещё?

Из школьного курса математики известно, что НОД можно найти из разложения чисел на простые множители.

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

Реализуем эту идею:

Первый if отлавливает ситуацию, когда оба числа делятся нацело на переменную цикла и, следовательно, переменная цикла является общим простым (!) множителем для обоих чисел и учитывается для вычисления НОД. Остальные два if отлавливают случаи, когда только одно из чисел делится на переменную цикла; эти множители в НОД не входят.

По-хорошему, цикл for должен перебирать только простые числа. Но нахождение простых чисел является самостоятельной вычислительной задачей, которую здесь решать не хотелось бы. Можно, конечно, использовать таблицу простых чисел, например, в пределах первой тысячи, а для больших чисел, в случае необходимости, вычислять простые числа проверкой на простоту. Но я не стал забираться в дебри факторизации натуральных чисел, а просто закрыл глаза на заведомо холостые проходы цикла for , когда переменная цикла не является простым числом, поскольку после нахождения любого из множителей хотя бы для одного из чисел цикл стартует заново.

Третий вариант по производительности не плох. Но пока это самопал. А что придумали умные люди за многовековую историю математики? «O’key, Гуг. то есть, Википедия, что такое НОД?» Вот, кстати, описано нахождение НОД через каноническое разложение на простые множители, которое мы уже реализовали. А вот что-то новенькое.

04 алгоритм Евклида (рекурсивный)

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

Реализуем рекурсивную версию:

Считается, что рекурсивные алгоритмы менее эффективны, чем итерационные, за счёт накладных расходов на вызов функции. Для проверки делаем и итерационный вариант.

05 алгоритм Евклида (итерационный)

Кстати, в Викиучебнике есть и другие реализации алгоритма Евклида.

06 бинарный алгоритм (рекурсивный)

1. НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
2. НОД(1, n) = 1; НОД(m, 1) = 1;
3. Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
4. Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
5. Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
6. Если m, n нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);
7. Если m, n нечётные и n REPEAT_TIMES раз. Время работы функции записывается в элемент массива, соответствующий этой функции. После того, как все тесты пройдены, результаты из массива делятся на количество наборов данных – получаем среднее время для набора.

Тестирование

Программа компилировалась под MS Visual Studio 2013 и TDM-GCC 4.8.1 в режиме 64-bit Release.

Как и ожидалось, первый алгоритм катастрофически неэффективен. Алгоритм №2 – минимальный костыль для №1 – работает почти в 2 раз быстрее.

Третий алгоритм неожиданно показал очень достойный результат: в 50 раз быстрее алгоритма №2.

Четвёртый и пятый варианты – алгоритм Евклида: рекурсивная версия, как ни странно, обогнала итерационную. По сравнению с третьим вариантом время улучшилось почти на порядок.

Бинарный алгоритм Евклида показал наилучшие результаты. Из трёх вариантов реализации рекурсивная версия – самая неторопливая. Наилучший результат у оптимизированной версии с использованием битовых операций.

Итого, самая производительная версия работает более чем в 2500 раз быстрее, чем изначальный вариант.

Примечание. Время, указанное в таблице – это время выполнения REPEAT_TIMES вызовов функции.

Выводы

Выводы достаточно банальны, но всё же:

1. Первый пришедший на ум алгоритм решения какой-то задачи часто неоптимален. Хотя и может правильно и достаточно приемлемо работать в определённых условиях.
2. Всегда надо попробовать подумать над усовершенствованием алгоритма или над альтернативным вариантом.
3. Учите математику!
4. Если есть возможность, посмотрите что сделали люди до вас. Может не стоит изобретать велосипед?
5. Оптимизируйте код.

Источник