Наибольший общий делитель или НОД легко отыскать по алгоритму Евклида, что появился еще в древности. Этот алгоритм служит для вычисления НОД двух натуральных чисел и основан на таком равенстве:

НОД (a, b) = НОД (a-b, b) = НОД(a, a-b).

Чтобы не иметь дело с отрицательными числами, обычно подменяют наибольшее число в паре. Существует рекурсивная и итеративная функции, что находят наибольший общий делитель пары чисел: Рекурсивная функция:

int NOD (int a, int b)

{

if (a == b)

return a;

if (a < b)

return NOD (a, b - a);

else return NOD (a – b, b);

}

Итеративная функция:

int NOD (int a, int b)

{

while (a != b)

{

if (a > b)

a-=b;

else b- = a;

}

return a;

}

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

int NOD (int a, int b)

{

while ((a != 0) && (b != 0))

{

if (a > b)

a = a%b;

else b = b%a;

}

return a+b;

}

В данном случае большее число заменяем остатком от деления большего числа на меньшее до тех пор пока остаток не станет равен нулю. Второе число и окажется нашим нодом.