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

Written on .

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.

форум firemonkey