НОД и НОК: алгоритмы и примеры кода

Изображение: визуальная иллюстрация понятия НОД и НОК для двух чисел

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

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

Короткое определение: алгоритм Евклида — итеративный (или рекурсивный) процесс, в котором на каждом шаге больший аргумент заменяется на остаток от деления на меньший, пока остаток не станет нулём; последний ненулевой делитель и есть НОД.

Пошаговый пример (75 и 50):

75 % 50 = 25 (остаток)
50 % 25 = 0 → процесс останавливается
НОД(75, 50) = 25

Важно: НОД(0, 0) формально не определён в большинстве задач; обычно считают его равным 0 по соглашению в программировании, но при математическом анализе этот случай рассматривают отдельно.

Рекурсивная реализация (пример)

Ниже — версии на популярных языках. Код сохранён в работоспособном виде.

// C++ program to find GCD/HCF of 2 numbers
#include 
using namespace std;

// Recursive function to find GCD/HCF of 2 numbers
int calculateGCD(int num1, int num2)
{
    if(num2==0)
    {
        return num1;
    }
    else
    {
        return calculateGCD(num2, num1%num2);
    }
}

// Driver Code
int main()
{
    int num1 = 34, num2 = 22;
    cout << "GCD of " << num1 << " and " << num2 << " is " << calculateGCD(num1, num2) << endl;

    int num3 = 10, num4 = 2;
    cout << "GCD of " << num3 << " and " << num4 << " is " << calculateGCD(num3, num4) << endl;

    int num5 = 88, num6 = 11;
    cout << "GCD of " << num5 << " and " << num6 << " is " << calculateGCD(num5, num6) << endl;

    int num7 = 40, num8 = 32;
    cout << "GCD of " << num7 << " and " << num8 << " is " << calculateGCD(num7, num8) << endl;

    int num9 = 75, num10 = 50;
    cout << "GCD of " << num9 << " and " << num10 << " is " << calculateGCD(num9, num10) << endl;

    return 0;
}

Вывод программы (пример):

GCD of 34 and 22 is 2
GCD of 10 and 2 is 2
GCD of 88 and 11 is 11
GCD of 40 and 32 is 8
GCD of 75 and 50 is 25

# Python program to find GCD/HCF of 2 numbers

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

# Driver Code
num1 = 34
num2 = 22
print("GCD of", num1, "and", num2, "is", calculateGCD(num1, num2))

num3 = 10
num4 = 2
print("GCD of", num3, "and", num4, "is", calculateGCD(num3, num4))

num5 = 88
num6 = 11
print("GCD of", num5, "and", num6, "is", calculateGCD(num5, num6))

num7 = 40
num8 = 32
print("GCD of", num7, "and", num8, "is", calculateGCD(num7, num8))

num9 = 75
num10 = 50
print("GCD of", num9, "and", num10, "is", calculateGCD(num9, num10))

// C program to find GCD/HCF of 2 numbers
#include 

// Recursive function to find GCD/HCF of 2 numbers
int calculateGCD(int num1, int num2)
{
    if(num2==0)
    {
        return num1;
    }
    else
    {
        return calculateGCD(num2, num1%num2);
    }
}

// Driver Code
int main()
{
    int num1 = 34, num2 = 22;
    printf("GCD of %d and %d is %d \n" , num1 , num2, calculateGCD(num1, num2));

    int num3 = 10, num4 = 2;
    printf("GCD of %d and %d is %d \n" , num3 , num4, calculateGCD(num3, num4));
    int num5 = 88, num6 = 11;
    printf("GCD of %d and %d is %d \n" , num5 , num6, calculateGCD(num5, num6));

    int num7 = 40, num8 = 32;
    printf("GCD of %d and %d is %d \n" , num7 , num8, calculateGCD(num7, num8));

    int num9 = 75, num10 = 50;
    printf("GCD of %d and %d is %d \n" , num9 , num10 , calculateGCD(num9, num10));

    return 0;
}

// JavaScript program to find GCD/HCF of 2 numbers

// Recursive function to find GCD/HCF of 2 numbers
function calculateGCD(num1, num2) {
    if(num2==0)
    {
        return num1;
    }
    else
    {
        return calculateGCD(num2, num1%num2);
    }
}

// Driver Code
var num1 = 34, num2 = 22;
document.write("GCD of " + num1 + " and " + num2 + " is " + calculateGCD(num1, num2) + "\n");

var num3 = 10, num4 = 2;
document.write("GCD of " + num3 + " and " + num4 + " is " + calculateGCD(num3, num4) + "\n");

var num5 = 88, num6 = 11;
document.write("GCD of " + num5 + " and " + num6 + " is " + calculateGCD(num5, num6) + "\n");

var num7 = 40, num8 = 32;
document.write("GCD of " + num7 + " and " + num8 + " is " + calculateGCD(num7, num8) + "\n");

var num9 = 75, num10 = 50;
document.write("GCD of " + num9 + " and " + num10 + " is " + calculateGCD(num9, num10) + "\n");

Альтернативы и практические заметки

Итеративная версия часто предпочтительнее рекурсивной, чтобы избежать переполнения стека при очень больших числах.
В C++17 и новее есть std::gcd (заголовок ) — используйте стандартную функцию для надёжности и читаемости.
В Python есть math.gcd — безопасно и быстро.
При вычислении НОК учитывайте знак чисел: обычно используют абсолютные значения, чтобы НОК был положительным.
При перемножении num1 num2 возможен целочисленный переполn при больших числах — используйте деление первым: (num1 / gcd) num2 или 128-битные типы, BigInt/long в зависимости от языка.

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

НОК (наименьшее общее кратное) двух чисел — наименьшее положительное целое число, которое делится на оба числа. Связь с НОД даёт удобную формулу:

LCM(num1, num2) = (|num1| / GCD(num1, num2)) * |num2|

Формула через произведение num1 * num2 / GCD корректна, но практики советуют сначала разделить на НОД, чтобы снизить риск переполнения.

Пример реализации и выводы

// C++ program to find LCM of 2 numbers
#include 
using namespace std;

// Recursive function to find LCM of 2 numbers
int calculateGCD(int num1, int num2)
{
    if(num2==0)
    {
        return num1;
    }
    else
    {
        return calculateGCD(num2, num1%num2);
    }
}

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

// Driver Code
int main()
{
    int num1 = 34, num2 = 22;
    cout << "LCM of " << num1 << " and " << num2 << " is " << calculateLCM(num1, num2) << endl;

    int num3 = 10, num4 = 2;
    cout << "LCM of " << num3 << " and " << num4 << " is " << calculateLCM(num3, num4) << endl;

    int num5 = 88, num6 = 11;
    cout << "LCM of " << num5 << " and " << num6 << " is " << calculateLCM(num5, num6) << endl;

    int num7 = 40, num8 = 32;
    cout << "LCM of " << num7 << " and " << num8 << " is " << calculateLCM(num7, num8) << endl;

    int num9 = 75, num10 = 50;
    cout << "LCM of " << num9 << " and " << num10 << " is " << calculateLCM(num9, num10) << endl;

    return 0;
}

Вывод (пример):

LCM of 34 and 22 is 374
LCM of 10 and 2 is 10
LCM of 88 and 11 is 88
LCM of 40 and 32 is 160
LCM of 75 and 50 is 150

(Аналогичные реализации для Python, C и JavaScript показаны выше; для краткости не дублируем код здесь.)

Важные случаи и отладка

Важно: всегда проверяйте нулевые и отрицательные аргументы.

НОД(a, 0) = |a| для любого целого a (включая отрицательные значения по модулю).
НОК(a, 0) обычно считается 0, если один аргумент равен 0 (поскольку нет положительного числа, кратного нулю и другому числу), но в практических задачах можно оговорить поведение.
Если оба аргумента равны 0, решите ожидаемое поведение вашего приложения (исключение, 0 или undefined).

Сложность и оценка производительности

Алгоритм Евклида имеет временную сложность примерно O(log min(a, b)) по количеству операций деления. Память — O(1) для итеративной версии, O(log n) для рекурсивной (из-за стека).

Ментальные модели и интуиция

НОД — это «набор общих простых множителей» с наибольшими степенями, встречающимися в обоих числах.
НОК — это «минимальный контейнер», который вмещает оба числа как набор простых множителей.
Связь: произведение чисел = НОД × НОК (с учётом модулей).

Практические рекомендации

Используйте встроенные функции, когда они доступны (std::gcd, math.gcd). Это уменьшит число ошибок.
Для очень больших чисел в C/C++ применяйте 128-битные целочисленные типы или библиотеки BigInt.
Предпочитайте итеративную реализацию в реальных системах для предотвращения переполнения стека.

Набор тестов и Критерии приёмки

Минимальные тест-кейсы, которые должны пройти реализации:

Обычные пары: (34,22) → НОД=2, НОК=374
Один аргумент ноль: (a,0) и (0,a) → НОД=|a|, НОК=0 или определено в ТЗ
Оба нуля: (0,0) → обработка по ТЗ (исключение или 0)
Отрицательные значения: (-12, 18) → НОД=6, НОК=36
Большие числа: тест на переполнение при расчёте НОК
Пары взаимно простых чисел: (13,17) → НОД=1, НОК=221

Критерии приёмки: реализация возвращает корректные математические значения для всех тест-кейсов, не вызывает переполнений и документирует поведение для случаев с нулями и отрицательными числами.

Шаблонный чеклист для ролей

Студент: реализовать и понимать алгоритм Евклида, уметь объяснить шаги.
Интервьюер: проверить граничные случаи, сложность, альтернативные реализации.
Инженер: выбрать итеративную версию, использовать встроенную библиотеку, учесть переполнение и обработку ошибок.

Быстрая диаграмма выбора метода

flowchart TD
  A[Нужно найти НОД/НОК?] --> B{Есть стандартная функция в языке?}
  B -- Да --> C[Использовать std/math.gcd]
  B -- Нет --> D{Ограничения по стеку?}
  D -- Да --> E[Итеративный алгоритм Евклида]
  D -- Нет --> F[Можно использовать рекурсивный алгоритм Евклида]
  C --> G[Для НОК использовать 'a/gcd'*b]
  E --> G
  F --> G

Контрпримеры и когда это не сработает

Прямое вычисление num1 * num2 / gcd приведёт к переполнению на больших числах; поэтому сначала делите на gcd.
Для чисел в плавающей точке эти методы неприменимы напрямую — требуется целочисленная арифметика или преобразование.

Короткая сводка

НОД вычисляют алгоритмом Евклида; сложность O(log min(a,b)).
НОК получают как (|a|/gcd)*|b|.
Обрабатывайте случаи с нулём и отрицательными числами, выбирайте итеративную реализацию для продакшена и используйте встроенные функции, когда они доступны.

Спасибо за чтение — попробуйте реализовать обе функции в любимом языке и проверьте их на описанных тест-кейсах.