Поиск НОД целых чисел PascalABC, FreePascal И.Г.Шматкова, учитель информатики ГУО «Гимназия 1 г.Слуцка»

Определение общего делителя двух натуральных чисел Пусть a, b, c – натуральные числа. Если a делится нацело на c и b делится нацело на c, то число с называется общим делителем чисел a и b. Общие делители чисел 18 и , 2, 3, 6. Общий делитель чисел 7 и (он единственный). Общие делители чисел 15, 20 и , 5.

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

Определение наибольшего общего делителя (НОД) Наибольшим общим делителем (НОД) двух чисел называется наибольший из их общих делителей (легко заметить, что наибольший общий делитель делится на любой другой общий делитель). НОД(14, 21)=7 НОД(25, 9)=1 НОД(1260, 825)=15

Определение взаимно простых чисел Два числа называют взаимно простыми, если их НОД равен 1 Взаимно простые числа: 25 и и и 392 Наглядное представление : если на плоскости построить « лес », установив на точки с целыми координатами « деревья », то из начала координат видны только деревья, координаты которых взаимно просты.

Свойства НОД Для натуральных чисел a и b (a > b) НОД(a, b)=НОД(a - b, b) НОД(a, a)=a НОД(a, 0)=a Попробуйте доказать данные свойства самостоятельно.

Задача Вводятся два натуральных числа N (N ). Определить НОД этих чисел. Решение: Из курса математики известен следующий алгоритм нахождения НОД двух чисел. Необходимо разложить оба числа на простые множители, затем найти произведение множителей, которые входят в оба разложения. Например, найдем НОД чисел 1260 и =2*2*3*3*5*7 825=3*5*5*11 НОД(1260, 825)=3*5=15 Данный алгоритм на практике обычно не применяется, так как разложение числа на простые множители является достаточно трудоемкой задачей, а еще потребуется найти среди них одинаковые. Поэтому применим метод, который называется алгоритмом Евклида. Первое описание алгоритма находится в « Началах » Евклида ( около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Однако этот алгоритм был открыт не Евклидом, так как упоминание о нём имеется уже в трудах Аристотеля. Для данного алгоритма существует множество теоретических и практических применений. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел.

Алгоритм Евклида Идея алгоритма: пока числа не равны, большее число заменять на разность большего и меньшего чисел. Понятно, что в качестве ответа можно взять любое из равных чисел. Выполним эту программу для следующих исходных данных: 1.a=55555 и b=44444 Ответ: a= и b= Ответ: 3 3.a= и b=1 Ответ: 1 4.a= и b=1 Ответ: ? Вы дождались ответа? Для уменьшения времени работы программы нужно что-то придумать!

Что можно заметить? Можно заметить, что для a= и b=1 одно и то же число, равное 1, нужно отнимать раз. Этого можно избежать, если вместо неоднократных вычитаний находить остаток от деления большего числа на меньшее. Действительно, НОД(a, b)=НОД(a mod b, b). Почему? Для окончания работы алгоритма нужно воспользоваться свойством НОД(a, 0)=a. В качестве ответа из чисел a и b следует взять то, которое не равно 0. Таким образом, мы увеличили скорость выполнения программы, заменив многократное вычитание одной командой нахождения остатка от деления ( для данного примера в раз ).

Алгоритм нахождения НОД (улучшенный)

Задача Вводятся четыре натуральных числа a, b, c, d (a, b, c, d ). Определить НОД этих чисел (наибольшее число, на которое делятся нацело все эти числа). Решение (приведем два способа): Можно найти НОД чисел a и b, затем НОД чисел c и d. Ответом будет НОД двух полученных чисел. Ответ=НОД(НОД(a,b),НОД(c,d)) Можно найти НОД чисел a и b, затем НОД полученного числа и с, потом НОД вновь полученного и d. Ответ=НОД(НОД(НОД(a,b),с),d) abcd НОД (a,b) НОД (c,d) НОД (a,b,c,d) abcd НОД (a,b) НОД (a,b,c) НОД (a,b,c,d)

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

Литература: 1. В.М. Котов и др. Информатика. Методы алгоритмизации: Учебное пособие 8-9 классов / В.М. Котов, И.А. Волков, А.И. Лапо. – Минск: Народная асвета, 2000.