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

Наибольший общий делитель Требуется составить программу определения наибольшего общего делителя ( НОД ) двух натуральных чисел. НОД (12, 18) = 6.

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

Идея алгоритма Евклида если M>N, то НОД ( М, N) = НОД ( М - N, N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности ( модуля их разности ) и меньшего числа.

Пусть К - общий делитель М u N (M> N). Это значит, что М = m К, N = n К, где m, n - натуральные числа, причем m > n. Тогда М - N = К (m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.

Второе свойство : НОД ( М, М ) = М.

Для " ручного " счета алгоритм Евклида выглядит так : 1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма ; 2) заменить большее число разностью большего и меньшего из чисел ; 3) вернуться к выполнению п. 1.

Рассмотрим этот алгоритм на примере М =32, N=24: Получили : НОД (32, 24) = НОД (8, 8) = 8, что верно.

Описание алгоритма Евклида блок - схемой

Программа на АЯ и на Паскале алг Евклид цел М, N нач вывод " Введите М и N" ввод М, N пока М N, повторять нц если M>N то M:=M-N иначе N:=N-M кв кц вывод "НОД=",М кон Program Evklid; var M, N: integer; begin writeln('Введите М и N'); readln(M, N); while MN do begin if M>N then M:=M-N else N:=N-M end; write('Н0Д=',М) end.