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

1. Вычислим r - остаток от деления числа a на b, a = bq+r, 0 <= r < b.

2. Если r = 0, то b есть искомое число.

3. Если r =/= 0, то заменим пару чисел (a,b) парой (b,r)
и перейдем к шагу 1.

// фукнция получения НОД
int NOD(int a, int b)
 {
 // пока числа не равны 0
 while(a!=0 && b!=0)
 {
 if(a>=b) a=a%b;
 else b=b%a;
 }
 return a+b; // Одно - ноль
                                }

При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.