Перечисленные равенства подсказывают идею алгоритма нахождения НОД: нужно от большего числа отниамть меншее до тех пор, пока они не станут равными, после чего НОД найдется по свойству 2)
Пример: НОД(530, 155)
Если проанализировать работу данного алгоритма, то можно заметить, что одно и то же число нужно отнимать несколько раз. Этого можно избежать, если вместо несколькиз вычитание находить остаток от деления большего числа на меньшее. В этом случае свойство 1) можно записать в виде Пример: НОД(530, 155)
a b
530 155
375 155
220 155
65 155
65 90
65 25
40 25
15 25
15 10
5 10
5 5
Алгоритм будет следующим:
while a<>b do
if a>b then a:=a-b else b:=b-a;
NOD:= a;
a b
530 155
65 155
65 25
15 25
15 10
5 10
5 0
Алгоритм будет выглядеть следующим образом:
while (a<>0) and (b<>0) do
if a>b then a:=a mod b else b:=b mod a;
if a=0 then NOD:= b else NOD:= a;
