Алгоритм Евклида на C: как найти НОД двух чисел циклом и рекурсией

Алгоритм Евклида находит наибольший общий делитель (НОД) двух целых чисел за O(log min(a, b)) операций. Это один из старейших известных алгоритмов — он описан ещё в «Началах» Евклида около 300 г. до н. э. — и при этом остаётся рабочим инструментом в криптографии, сокращении дробей и вычислении НОК.

Ниже — две реализации на чистом C (без C++-конструкций), разбор того, почему алгоритм работает, и разбор ошибок, которые чаще всего допускают новички.

Что такое НОД и зачем он нужен​

Наибольший общий делитель gcd(a, b) — самое большое натуральное число, на которое делятся без остатка и a, и b. Примеры:

• gcd(12, 18) = 6
  
• gcd(7, 13) = 1 (числа взаимно просты)
  
• gcd(0, 5) = 5
  
• gcd(0, 0) — формально не определён, но на практике удобно считать равным 0
  

НОД используется при сокращении дробей, в модульной арифметике (расширенный алгоритм Евклида находит обратный элемент по модулю), при вычислении НОК через формулу lcm(a, b) = a / gcd(a, b) * b.

Математическая основа​

Ключевое свойство, на котором строится алгоритм:

gcd(a, b) = gcd(b, a mod b)

Почему это верно? Если g делит и a, и b, то g делит и остаток a mod b = a − ⌊a/b⌋·b. Обратно: если g делит b и a mod b, то g делит и a = ⌊a/b⌋·b + (a mod b). Значит, множества общих делителей пар (a, b) и (b, a mod b) совпадают, а следовательно, совпадают и их наибольшие элементы.

Процесс повторяется до тех пор, пока одно из чисел не станет нулём. Когда b = 0, ответ — a.

Рекурсивная реализация​

#include <stdio.h>

int gcd_recursive(int a, int b) {
    if (b == 0)
        return a;
    return gcd_recursive(b, a % b);
}

int main(void) {
    printf("gcd(48, 18) = %d\n", gcd_recursive(48, 18));
    printf("gcd(7, 13)  = %d\n", gcd_recursive(7, 13));
    printf("gcd(0, 5)   = %d\n", gcd_recursive(0, 5));
    return 0;
}

Вывод:

gcd(48, 18) = 6
gcd(7, 13)  = 1
gcd(0, 5)   = 5

Как работает рекурсия на примере gcd(48, 18)​

Шаг	a	b	a % b
1	48	18	12
2	18	12	6
3	12	6	0
4	6	0	—

На четвёртом шаге b = 0, рекурсия останавливается и возвращает a = 6.

Итеративная реализация​

Цикл делает то же самое без стека вызовов:

#include <stdio.h>

int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main(void) {
    printf("gcd(48, 18) = %d\n", gcd_iterative(48, 18));
    printf("gcd(100, 75) = %d\n", gcd_iterative(100, 75));
    return 0;
}

Итеративная версия предпочтительна, когда глубина рекурсии может стать проблемой (хотя для 32-битных целых она не превышает ~45 вызовов, что безопасно).

Сложность и худший случай​

Алгоритм работает за O(log min(a, b)). Точную верхнюю границу даёт теорема Ламе: если b < F_n (n-е число Фибоначчи), алгоритм выполнит не более n − 2 рекурсивных вызовов. Худший вход — последовательные числа Фибоначчи: gcd(F_n, F_{n−1}) делает ровно n − 2 шагов.

Поскольку числа Фибоначчи растут экспоненциально, количество шагов логарифмически зависит от входных данных. Для 32-битных int максимум — около 45 итераций, для 64-битных — около 93.

Работа с отрицательными числами​

Оператор % в C для отрицательных чисел возвращает результат со знаком делимого (начиная с C99 это гарантировано стандартом). Чтобы функция корректно работала с любыми знаками, достаточно взять модули на входе:

#include <stdio.h>

static int abs_val(int x) {
    return x < 0 ? -x : x;
}

int gcd_abs(int a, int b) {
    a = abs_val(a);
    b = abs_val(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main(void) {
    printf("gcd(-48, 18) = %d\n", gcd_abs(-48, 18));
    printf("gcd(-48, -18) = %d\n", gcd_abs(-48, -18));
    return 0;
}

Оба вызова вернут 6.

Внимание: abs_val(INT_MIN) приводит к неопределённому поведению, потому что −INT_MIN не представим в int. Если нужен полный диапазон, используйте long long или беззнаковый тип.

Вычисление НОК через НОД​

Наименьшее общее кратное связано с НОД формулой:

lcm(a, b) = a / gcd(a, b) * b

Деление выполняется до умножения, чтобы снизить риск переполнения:

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    return a / gcd(a, b) * b;
}

int main(void) {
    printf("lcm(4, 6) = %d\n", lcm(4, 6));   /* 12 */
    printf("lcm(3, 7) = %d\n", lcm(3, 7));   /* 21 */
    return 0;
}

Для больших значений даже порядок a / gcd * b не спасает от переполнения int — в таких случаях переходите на long long или проверяйте результат до умножения.

НОД нескольких чисел​

Функция gcd ассоциативна: gcd(a, b, c) = gcd(gcd(a, b), c). Это позволяет вычислять НОД массива последовательно:

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int gcd_array(const int *arr, int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = gcd(result, arr[i]);
        if (result == 1)
            break;  /* дальше уменьшать некуда */
    }
    return result;
}

int main(void) {
    int nums[] = {12, 18, 24};
    printf("gcd(12, 18, 24) = %d\n", gcd_array(nums, 3));  /* 6 */
    return 0;
}

Ранний выход при result == 1 экономит время на больших массивах: суммарная сложность обработки n чисел, не превосходящих C, составляет O(n + log C), а не O(n · log C), потому что каждая нетривиальная итерация уменьшает текущий кандидат как минимум вдвое.

Бинарный алгоритм Евклида (оптимизация)​

Операция взятия остатка % на некоторых процессорах заметно медленнее побитовых сдвигов и вычитаний. Бинарный GCD заменяет деление на сдвиги, используя три свойства:

• gcd(2a, 2b) = 2 · gcd(a, b)
  
• gcd(2a, b) = gcd(a, b), если b нечётно
  
• gcd(a, b) = gcd(b, a − b), если оба нечётны
  

#include <stdio.h>

int gcd_binary(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    /* Находим общий множитель 2 */
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }

    /* Убираем оставшиеся двойки из a */
    while ((a & 1) == 0)
        a >>= 1;

    do {
        /* Убираем двойки из b */
        while ((b & 1) == 0)
            b >>= 1;

        /* Теперь оба нечётны: вычитаем меньшее из большего */
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        b -= a;
    } while (b != 0);

    return a << shift;
}

int main(void) {
    printf("gcd_binary(48, 18) = %d\n", gcd_binary(48, 18));  /* 6 */
    printf("gcd_binary(100, 75) = %d\n", gcd_binary(100, 75)); /* 25 */
    return 0;
}

На практике выигрыш заметен в горячих циклах (криптография, обработка больших массивов). Для учебных задач достаточно классической версии с %.

Типичные ошибки начинающих​

Ошибка	Последствие	Исправление
Забыть базовый случай b == 0 в рекурсии	Бесконечная рекурсия, переполнение стека	Всегда проверять if (b == 0) return a;
Передать отрицательные числа без обработки	Неверный результат или зацикливание на некоторых платформах	Брать модуль на входе
Перепутать порядок a % b и b % a	Лишняя итерация, но результат верный (алгоритм сам исправится)	Не критично, но лучше сразу передавать большее первым
Вычислять НОК как a * b / gcd(a, b)	Переполнение при больших a и b	Сначала делить: a / gcd(a, b) * b
Использовать int для чисел, близких к INT_MAX	Переполнение в промежуточных вычислениях	Перейти на long long или unsigned

Проверка результата​

Простейший способ убедиться, что функция работает корректно — проверить, что возвращённое значение делит оба аргумента и что частные взаимно просты:

#include <stdio.h>
#include <assert.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

void check_gcd(int a, int b) {
    int g = gcd(a, b);
    assert(g > 0);
    assert(a % g == 0);
    assert(b % g == 0);
    assert(gcd(a / g, b / g) == 1);
}

int main(void) {
    check_gcd(48, 18);
    check_gcd(100, 75);
    check_gcd(7, 13);
    check_gcd(0, 42);
    printf("All checks passed.\n");
    return 0;
}

Итоговый чек-лист​

• Выберите итеративную версию для продакшена и рекурсивную для понимания принципа.
  
• Обрабатывайте отрицательные числа и случай (0, 0) явно.
  
• Для НОК делите до умножения.
  
• Для массива чисел используйте ассоциативность и ранний выход при единице.
  
• Если % становится узким местом — переходите на бинарный GCD.
  
• Проверяйте результат: g делит оба числа, а частные взаимно просты.
  

Источники​

• Euclidean algorithm for computing the greatest common divisor - Algorithms for Competitive Programming
  
• Main Page - Algorithms for Competitive Programming