НОД (Наибольший общий делитель)

Английский эквивалент этого понятия GCD(Greatest Common Divisor). Краткую теорию по этому вопросу читаем на Wikipedia. Сразу отметим, что наиболее эффективный и распространенный алгоритм нахождения НОДа является алгоритм Евклида, о котором очень популярно изложено сайте MAXimal. Обратите внимание на доказательство корректности алгоритма.
После ознакомления с этой статьей предлагаю перейти к практической части.
По мотивам введения первой главы книги Левитина “Алгоритмы. Введение в разработку и анализ” рассмотрим несколько реализаций нахождения НОДа.
1. Рекурсивная реализация алгоритма Евклида:

1. int gcd_Euclid(int a, int b)
2. {
3.   if (b == 0)
4.     return a;
5.   return gcd_Euclid(b,a%b);
6. }