НОД и НОК

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

Немного теории

Для начала вспомним немного теории. В выражении деления А / В = С, А называется делимым, В - делителем, а С - частным.

Число В можно назвать множителем или делителем числа А, если А делится на В. Например, делителями числа 18 будут 1, 2, 3, 6, 9 и 18.

Целое число называется простым, если среди его делителей присутствует только 1 и само это число. Например, число 11 делится только на 1 и 11 - оно простое. Число 10 делится на 1, 5 и 10 - оно не является простым.

Любое число можно единственным образом разложить на простые множители. Например, число 12 = 2 * 2 * 3. Число 13 = 1 * 13.

Разложение на множители

И НОК и НОД можно найти с помощью разложения на множители, поэтому сначала рассмотрим как число N можно представить в виде списка множителей. Для этого посмотрим на некоторое число, например 12.

Начиная раскладывать число на множители, мы пытаемся делить его на простые числа, начиная с 2. Если число делится на 2, записываем в список множителей 2, а число делим на 2. В итоге число станет равно 6. Пока число все еще делится на 2, продолжаем делить. 6 делится на 2, записываем в список еще раз 2, число теперь равно 3. На 2 число не делится, начинаем делить на следующее число - 3. Число 3 делится на 3, записываем в список 3, число теперь равно 1.

Таким образом, алгоритм разложения на множители следующий. Пока число делится на 2, делим на 2. Пока делится на 3, делим на 3 и т.д. Повторяем до тех пор, пока число больше 1.

Примеры метода factors

НОД

Наибольший общий делитель(НОД) двух чисел А и В - это наибольшее число, которое делит нацело и А, и В. Например, для чисел 18 и 12 НОД(18, 12) = 6.

Полный перебор

Метод перебора работает всегда и везде, если мы не торопимся. Мы берем наименьшее из двух чисел (наименьшее точно не делится на наибольшее) и пытаемся разделить А и В на это число. Если получилось - НОД найдет. Если нет - уменьшаем число на 1 и пробуем опять. Повторяем пока число больше 0. Если мы дошли до 0, то числа взаимно простые и их НОД = 1.

Используя множители

Чуть раньше мы не зря научились раскладывать числа на множители. Этот умение сейчас очень пригодится.

Рассмотрим разложение на множители для чисел 18 и 12

• 18 = 2 * 3 * 3
• 12 = 2 * 3

Мы уже знаем, что НОД(18, 12) = 6. Чуть выше можно заметить, что в разложении чисел есть одинаковые множители. В данном примере это 2 * 3. Эти общие множители, точнее их произведение, и есть НОД.

Умея раскладывать на множители, задача сводится к нахождению общих вхождений чисел в список множителей числа. Это можно сделать несколькими способами, например с помощью Hashmap, в котором ключ - это множитель, а значение - число вхождений этого множителя .

Сначала создадим Hashmap, пройдемся по списку множителей и добавим или 1, если по данному ключу еще ничего не лежит, или увеличим значение на 1, если значение по данному ключу существует. Так, например для списка множителей [2, 2, 3] получим следующий HashMap {2=2, 3=1}

После получения 2-х Hashmap, проходим по всем ключам любого и смотрим, есть ли такой ключ в другом. Если есть - нам нужно выбрать наименьшее значение по заданному ключу. Например, для 2-х Hashmap aMap{2=1, 3=2} и bMap{2=3, 5=1} для ключа 2 берем только значение 1 (минимум из 1 и 3). Добавляем это число в результирующий список.

Так мы получим все числа, которые есть как в первом, так и во втором списке

Метод нахождения НОД теперь крайне прост. Нужно перемножить все числа (если список не пустой)

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

Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».

Посмотрим на решение задачи НОД немного с другого угла.

На изображении выше представлены ряд из 18 квадратов, и ряд из 12. Для нахождения НОД этих двух рядов, нужно найти такое число, из которого можно составить оба ряда, причем это число должно быть максимальным из возможных.

Например, это можно сделать с помощью ряда из квадратов(точнее прямоугольников) размером 2. Такие прямоугольники в данном случае - делители числа.

А можно из ряда размером 6. Это максимальная длина прямоугольника, из которого можно составить оба ряда.

Попробуем изобразить ряд из 18 и 12 квадратов немного другим способов

Мы представили 18 как 12 + 6. При таком раскладе можно не учитывать первую (целую строку) при вычислении НОД, иными словами НОД(18, 12) = НОД(6, 12).

Можно продолжить эту логику, и найти НОД(6, 12)

Теперь длины обоих рядов совпадают, поэтому мы нашли НОД. Итак, НОД(6, 12) = НОД(18, 12) = 6.

В общем случае, когда А > В, НОД(А, В) = НОД(А % В, В).

В этом и состоит алгоритм Евклида.

В коде он выглядит следующим образом (вывод в консоль только для представления выполнения)

Если число а больше, чем b, то метод отработает как нужно. Иначе первым шагом gcd поменяет значения a и b, т.к. a % b при b > a = a.

НОД

Наименьшее общее кратное(НОК) чисел А и В - это минимальное число, которое делится на А и В без остатка. Например, для чисел 18 и 12 НОК(18, 12) = 36 (36 / 18 = 2, 36 / 12 = 3)

Полный перебор

Традиционный способ - brute force. Увеличиваем число, пока оно не будет делить и а, и b.

Используя множители

Вспомним, что

• 18 = 2 * 3 * 3 = (2 * 3) * 3
• 12 = 2 * 2 * 3 = (2 * 3) * 2

Число, которое является НОК должно делиться на оба числа. Поэтому это число должно делиться на общую часть обоих чисел (в данном случае это 2 * 3), а также на все числа, которые есть в а, но нет в b, и наоборот.

Нахождение общей части двух списков множителей у нас уже есть, реализовать ту часть, которая находит из списка множителей числа список уникальных множителей, которые не присутствуют в общем списке можно также используя Hashmap. Не будем останавливаться на этом способе, т.к. есть способ лучше

НОК зная НОД

НОК(А, В) можно найти как (А * В) / (НОД(A, B)). Почему это так?

Опять разложим 18 как (2 * 3) * 3, а 12 как (2 * 3) * 2

НОК вычисляется как (2 * 3) * 3 * 2, т.е. общая часть двух списков множителей, умноженная на уникальную часть каждого списка.

НОД вычисляется как общая часть двух списков множителей, т.к. в данном случае это (2 * 3).

Собираем все вместе: НОК(18, 12) = ((2 * 3) * 3) * ((2 * 3) * 2) / (2 * 3) = (2 * 3) * 2 * 3.

Иными словами, А * В - это НОК, умноженный на общий список множителей чисел А и В, или А * В = НОК(А, В) * НОД(А, В).

Зачем это все

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

• НОД при сокращение дробей в математических расчетах
• НОК для приведение дробей к общему знаменателю в математических расчетах
• Для нахождения взаимно простых чисел (для таких чисел НОД(А, В) = 1)
• Некоторый вариант алгоритма Евклида (расширенный алгоритм Евклида) используется для решения некоторых видов уравнений