Найти наибольший общий делитель для двух 80-значных натуральных чисел

Постановка задачи

Найти наибольший общий делитель для двух 80-значных натуральных чисел.

Теоретическая часть

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

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

Переборный алгоритм

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

До тех пор пока d не разделится на оба числа без остатка, уменьшаем его на единицу.

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

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

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

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений, при построении непрерывных дробей, в методе Штурма.

Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например, таких, как «теорема Лагранжа о сумме четырёх квадратов» и «основная теорема арифметики».

1. Березин Б.И., Березин С.Б. Начальный курс С и С++. – М.: ДИАЛОГ-МИФИ, 2011, 288 с.
2. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. – Харьков: Фолио, Ростов н/Д: Феникс, 2010, 359 с.
3. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. – Харьков: Фолио, Ростов н/Д: Феникс, 2010, 359 с.
4. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. – М.: Мир, 2012, 320 с.
5. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 2012, 358 с.
6. Задачи по программированию / С. А. Абрамов, Г. Г. Гнездилова, Е. Н. Капустина, М. И. Селюн. – М.: Наука, 2010, 224 с.
7. Касаткин В. Н. Информация. Алгоритмы. ЭВМ. – М.: Просвещение, 2010, 192 с.
8. Керниган Б., Ритчи Д. Язык программирования Си: Пер. с англ. – М.: Финансы и статистика, 2013, 272 с.
9. Миков А. И. Информатика. Введение в компьютерные науки. – Пермь: Изд-во ПГУ, 2012, 322 с.
10. Могилев А. В., Пак Н.И., Хеннер Е.К. Информатика: Учеб. пособие для студ. пед. вузов / Под ред. Е. К. Хеннера. – М.: Изд. центр «Академия», 2011, 848 с.