НОД и НОК двух чисел

Почему это полезно

Математика лежит в основе многих алгоритмов. Знание НОД и НОК полезно при решении задач с рациональными числами, планировании периодов, криптографии и при подготовке к интервью по программированию.

Краткое определение

НОД: наибольшее положительное целое, которое делит оба числа без остатка.
НОК: наименьшее положительное целое, которое делится на оба числа.

Как найти НОД двух чисел

Алгоритм: Евклидов алгоритм. Берём большее число и делим на меньшее. Заменяем пару (a, b) на (b, a % b) и повторяем, пока остаток не станет 0. Последний ненулевой делитель — НОД.

Пример: НОД(75, 50)

75 % 50 = 25
50 % 25 = 0
НОД = 25

Вычислительная сложность: O(log min(a, b)) — где a и b — абсолютные значения входных чисел.

C++: рекурсивная реализация НОД

// C++ программа для вычисления НОД двух чисел
#include 
using namespace std;

// Рекурсивная функция для НОД
int calculateGCD(int num1, int num2)
{
    if (num2 == 0)
    {
        return num1;
    }
    else
    {
        return calculateGCD(num2, num1 % num2);
    }
}

int main()
{
    int num1 = 34, num2 = 22;
    cout << "НОД " << num1 << " и " << num2 << " = " << calculateGCD(num1, num2) << endl;

    int num3 = 10, num4 = 2;
    cout << "НОД " << num3 << " и " << num4 << " = " << calculateGCD(num3, num4) << endl;

    int num5 = 88, num6 = 11;
    cout << "НОД " << num5 << " и " << num6 << " = " << calculateGCD(num5, num6) << endl;

    int num7 = 40, num8 = 32;
    cout << "НОД " << num7 << " и " << num8 << " = " << calculateGCD(num7, num8) << endl;

    int num9 = 75, num10 = 50;
    cout << "НОД " << num9 << " и " << num10 << " = " << calculateGCD(num9, num10) << endl;

    return 0;
}

Выход программы:

НОД 34 и 22 = 2
НОД 10 и 2 = 2
НОД 88 и 11 = 11
НОД 40 и 32 = 8
НОД 75 и 50 = 25

Python: рекурсивная реализация НОД

# Python программа для вычисления НОД двух чисел

def calculateGCD(num1, num2):
    if num2 == 0:
        return num1
    else:
        return calculateGCD(num2, num1 % num2)

# Примеры
print("НОД", 34, "и", 22, "=", calculateGCD(34, 22))
print("НОД", 10, "и", 2, "=", calculateGCD(10, 2))
print("НОД", 88, "и", 11, "=", calculateGCD(88, 11))
print("НОД", 40, "и", 32, "=", calculateGCD(40, 32))
print("НОД", 75, "и", 50, "=", calculateGCD(75, 50))

Выход:

НОД 34 и 22 = 2
НОД 10 и 2 = 2
НОД 88 и 11 = 11
НОД 40 и 32 = 8
НОД 75 и 50 = 25

C: рекурсивная реализация НОД

// C программа для вычисления НОД двух чисел
#include 

int calculateGCD(int num1, int num2)
{
    if (num2 == 0)
    {
        return num1;
    }
    else
    {
        return calculateGCD(num2, num1 % num2);
    }
}

int main()
{
    int num1 = 34, num2 = 22;
    printf("НОД %d и %d = %d\n", num1, num2, calculateGCD(num1, num2));

    int num3 = 10, num4 = 2;
    printf("НОД %d и %d = %d\n", num3, num4, calculateGCD(num3, num4));

    int num5 = 88, num6 = 11;
    printf("НОД %d и %d = %d\n", num5, num6, calculateGCD(num5, num6));

    int num7 = 40, num8 = 32;
    printf("НОД %d и %d = %d\n", num7, num8, calculateGCD(num7, num8));

    int num9 = 75, num10 = 50;
    printf("НОД %d и %d = %d\n", num9, num10, calculateGCD(num9, num10));

    return 0;
}

JavaScript: рекурсивная реализация НОД

// JavaScript программа для вычисления НОД двух чисел
function calculateGCD(num1, num2) {
    if (num2 == 0) {
        return num1;
    } else {
        return calculateGCD(num2, num1 % num2);
    }
}

console.log("НОД", 34, "и", 22, "=", calculateGCD(34, 22));
console.log("НОД", 10, "и", 2, "=", calculateGCD(10, 2));
console.log("НОД", 88, "и", 11, "=", calculateGCD(88, 11));
console.log("НОД", 40, "и", 32, "=", calculateGCD(40, 32));
console.log("НОД", 75, "и", 50, "=", calculateGCD(75, 50));

Как найти НОК двух чисел

Формула связывает НОК и НОД:

num1 * num2 = НОК(num1, num2) * НОД(num1, num2)
НОК(num1, num2) = (num1 / НОД(num1, num2)) * num2

Эта формула удобна, потому что сначала быстро находим НОД, затем вычисляем НОК. Деление num1 / gcd делается в целых числах, чтобы снизить риск переполнения при больших num1 и num2.

C++ реализация НОК

// C++ программа для НОК
#include 
using namespace std;

int calculateGCD(int num1, int num2)
{
    if (num2 == 0)
        return num1;
    return calculateGCD(num2, num1 % num2);
}

int calculateLCM(int num1, int num2)
{
    return (num1 / calculateGCD(num1, num2)) * num2;
}

int main()
{
    cout << "НОК 34 и 22 = " << calculateLCM(34, 22) << endl;
    cout << "НОК 10 и 2 = " << calculateLCM(10, 2) << endl;
    cout << "НОК 88 и 11 = " << calculateLCM(88, 11) << endl;
    cout << "НОК 40 и 32 = " << calculateLCM(40, 32) << endl;
    cout << "НОК 75 и 50 = " << calculateLCM(75, 50) << endl;
    return 0;
}

Выход:

НОК 34 и 22 = 374
НОК 10 и 2 = 10
НОК 88 и 11 = 88
НОК 40 и 32 = 160
НОК 75 и 50 = 150

(аналогичные реализации на Python, C и JavaScript похожи на примеры для НОД; меняется только формула вычисления НОК)

Альтернативы и усовершенствования

Итеративный Евклидов алгоритм часто предпочтительней, чтобы избежать переполнения стека при очень больших числах.
Бинарный алгоритм (Stein) использует побитовые операции и на практике быстрее для очень больших целых чисел.
В Python есть встроенная функция math.gcd — используйте её для надёжности и читаемости.
Для языков без больших целых (например, C со стандартным int) учитывайте переполнение: применяйте 64-битные типы или BigInteger-аналог.

Когда алгоритм может «провалиться» или дать неправильный результат

Неправильная работа с нулём: НОД(0, 0) математически не определён, но на практике часто задают 0. Решение: явно обрабатывать случай, когда оба числа равны 0.
Отрицательные входы: применяйте абсолютные значения перед вычислением.
Переполнение при умножении num1 * num2 для формулы НОК: делите сначала на НОД, затем умножайте.

Важно: для целых типов используйте (num1 / gcd) num2, а не (num1 num2) / gcd.

Тесты и критерии приёмки

Критерии приёмки функции calculateGCD / calculateLCM:

Работает для положительных и отрицательных целых (результат положителен).
Обрабатывает случаи, когда одно из чисел равно 0.
Не переполняет тип (см. тесты на большие значения).
Соответствует математическим примерам (см. тестовые пары ниже).

Тестовые случаи:

(34, 22) -> НОД=2, НОК=374
(10, 2) -> НОД=2, НОК=10
(88, 11) -> НОД=11, НОК=88
(40, 32) -> НОД=8, НОК=160
(75, 50) -> НОД=25, НОК=150
(0, n) для n>0 -> НОД = |n|, НОК = 0
(0, 0) -> спецификация: возвращать 0 или бросать исключение — выберите одно и документируйте

Чек-листы по ролям

Для интервьюера:

Проверьте корректность на простых примерах.
Попросите описать сложность алгоритма.
Спросите про обработку нуля и отрицательных чисел.

Для разработчика:

Используйте итеративную версию, если нужна стабильность.
Для больших чисел проверяйте типы (64-bit / BigInt).
Добавьте модульные тесты для краевых случаев.

Краткие эвристики и ментальные модели

НОД — это «наибольшая общая часть», НОК — «первый общий шаг» периодов.
Евклид — эффективен: каждый шаг значительно уменьшает числа.
Чтобы избежать переполнения при НОК, делите до умножения.

1-строчная глоссарий

Евклидовый алгоритм: метод нахождения НОД через повторяющиеся деления с остатком.

Часто задаваемые вопросы

Что возвращать для НОД(0, 0)?

Документируйте поведение: либо возвращать 0, либо выбрасывать ошибку. В математике значение не определено.

Можно ли использовать встроенные функции?

Да. В Python используйте math.gcd. В JavaScript для больших чисел используйте BigInt и собственную реализацию или библиотеки.

Итог

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

Важно: протестируйте реализацию на краевых случаях и выберите подходящий тип данных для входов.