Наибольший общий делитель двух чисел.

НОД двух чисел А и В – это макимальное число, на которое делится и А, и В.

Например:

НОД (14, 21) = 7, НОД (16, 24) = 8.

Давайте составим процедуру, для нахождения НОД двух чисел. Как это сделать?! Подумайте, прежде чем читать дальше! Ещё раз внимательно прочитайте определение.

Так как найденный делитель должен быть общим, то на него должно делиться и первое число, и второе. Кроме того, нам нужен максимальный такой делитель. Если мы будем перебирать все общие делители в возрастающем порядке, то интересующий нас делитель будет последним. Переведём всё сказанное с русского языка на Паскаль:

Procedure NOD (a, b : integer; var rez : integer);

Var i : integer;

Begin

For i := 1 to a do

If (a mod i = 0) and (b mod i = 0)

Then rez := i;

End;

Составьте самостоятельно программу, которая будет использовать эту процедуру.