Нок наибольшее общее кратное как найти

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

Наибольший общий делитель (НОД)

Если натуральное число a делится на натуральное число bb, то bb называют делителем числа aa, а число aa называют кратным числа bb. aa и bb являются натуральными числами. Число gg называют общим делителем и для aa и для bb. Множество общих делителей чисел aa и bb конечно, так как ни один из этих делителей не может быть больше, чем aa. Значит, среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел aa и bb и для его обозначения используют записи: НОД (a;b)(a;b) или D(a;b)(a;b)

Пример
Наибольший общий делитель (НОД) чисел 1818 и 2424 — это 66.

Как найти наибольший общий делитель (НОД)

Существует несколько способов нахождения наибольшего общего делителя (НОД) двух или более целых чисел:

• Алгоритм Евклида: НОД(a,b)=(a, b) = НОД (b,a(b, a mod b)b), где «mod» — это операция взятия остатка от деления большего числа на меньшее. Этот алгоритм можно продолжать до тех пор, пока одно из чисел не станет равно нулю. В этом случае НОД равен ненулевому числу.

Пример
НОД(18,24)=НОД(24,18)=НОД(18,6)=НОД(6,0)=6НОД(18, 24) = НОД(24, 18) = НОД(18, 6) = НОД(6, 0) = 6

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

Пример
НОД(60,84)=22⋅31=12(60, 84) = 2^{2} cdot 3^{1} = 12, так как общие простые множители −2- 2 и 33, их минимальные степени −2- 2 и 11 соответственно.

• Таблица делителей: Составить таблицы всех делителей каждого числа и найти наибольшее общее число, которое является делителем обоих чисел. Этот метод не рекомендуется для больших чисел, так как он требует много времени и усилий.

Наименьшее общее кратное (НОК)

Общими кратными чисел называются числа которые делятся на исходные без остатка. Например для чисел 2525 и 5050 общими кратными будут числа 50,100,150,20050,100,150,200 и т.д Наименьшее из общих кратных будет называться НОК и обозначается НОК(a;b)(a;b) или K(a;b).(a;b).

Пример
Наименьшее общее кратное чисел 88 и 1212 – это 2424. Т.е. НОК (8,12)=24(8, 12) = 24.

Как найти наименьшее общее кратное (НОК)

Чтобы найти НОК двух чисел, необходимо:

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

Пример
Рассмотрим два числа: 88 и 1212. Найдем их НОКНОК:

• Разложим 88 и 1212 на простые множители: 8=23,12=22⋅38 = 2^3, 12 = 2^2 cdot 3.
• Выпишем все простые множители: 23⋅32^3 cdot 3.
• Для каждого простого множителя выберем наибольшую кратность: 232^3 и 33.
• Умножим выбранные простые множители между собой: 23⋅3=242^3 cdot 3 = 24.

Таким образом, НОК чисел 88 и 1212 равен 2424.

Свойства НОД и НОК

• Любое общее кратное чисел aa и bb делится на K(a;b)(a;b);
• Если a⋮bavdots b , то К(a;b)=a(a;b)=a;
• Если К(a;b)=k(a;b)=k и mm-натуральное число, то К(am;bm)=km(am;bm)=km. Если dd-общий делитель для aa и bb,то К(ad;bdfrac{a}{d};frac{b}{d})= kd frac{k}{d}
• Если a⋮cavdots c и b⋮cbvdots c ,то abcfrac{ab}{c} — общее кратное чисел aa и bb;
• Для любых натуральных чисел aa и bb выполняется равенство D(a;b)⋅К(a;b)=abD(a;b)cdot К(a;b)=ab;
• Любой общий делитель чисел aa и bb является делителем числа D(a;b)D(a;b).

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

1 Алгоритм расчета наибольшего общего делителя

Даны два целых числа A и B, их наибольший общий делитель — такое число C, что на него делится без остатка и A, и B

В школе нас учили искать НОД разложением на простые множители, однако такая задача крайне тяжело решается на компьютере, зато мы можем заставить его перебрать все числа от min(a, b) до единицы и проверить условие делимости, однако и это не самый эффективный способ.

Люди, интересующиеся алгоритмами, сразу вспомнять алгоритм Евклида, однако, на мой взгляд, нет смысла зубрить алгоритмы — наиболее ценно их понимание и способность разработать нечто аналогичное. Для этого я предлагаю пытаться визуализировать задачу.

Целое число — это количество чего-либо неделимого. На следующей картинке два числа показаны в виде прямоугольников, под значением числа можно понимать количество «блоков в прямоугольнике». Показано схематично (я не пытался рисовать точно).

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

Эффективный алгоритм расчета НОД строится на следующих наблюдениях (постарайтесь их «почувствовать»):

1. если A делится на B без остатка — то НОД(A, B) = B;
2. любое число, которое делит оба числа A и B, делит также и A-B, поэтому
   НОД(A, B) <= НОД (A — B, B);. То есть уменьшение числа A на значение B не повлияет на результат вычисления НОД;
3. мы можем воспользоваться предыдущим пунктом несколько (t) раз — если A = B*t + r для целых чисел t и r — то НОД(A, B) = НОД(r, B).

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

В какой-то момент числа окажутся равны и мы получим результат. Этот момент обязательно настанет — в крайнем случае когда оба числа станут равны единице (потому что это ей кратны любые целые числа).

Из последней иллюстрации видно, что многократное вычитание можно заменить на получение остатка от деления (об этом же говорит третье «наблюдение»). Тогда алгоритм можно записать на псевдокоде следующим образом:

наибольший_общий_делитель(a, b) {
  если a делится на b без остатка то - верни b;
  если b делится на a без остатка то - верни a;
  
  если a > b - то верни наибольший_общий_делитель(a mod b, b);
  иначе верни наибольший_общий_делитель(a, b mod a);
}

Тут mod — операция получения остатка от деления.

2 Алгоритм расчета наименьшего общего кратного

Наименьшее общее кратное двух целых чисел A и B есть наименьшее натуральное число, которое делится на A и B без остатка.

Чтобы лучше понять о чем речь — предлагаю такую геометрическую интерпретацию: значения A и B задают длины отрезков. НОК — это длина другого отрезка, который можно составить как из целого количества отрезков A, так и отрезков B:

Для любых чисел мы можем найти общее кратное C = A*B, однако, оно не всегда будет наименьшим. Примитивный алгоритм вычисления НОК мог бы заключаться в переборе всех чисел от max(A, B) до A*B. Однако, это не самое эффективное решение. На самом деле, если длина отрезка A = 4, а B = 3, то перебирать надо все отрезки, кратные 4, т.е. max(A, B).

Обратите снимание, что если A и B взаимнопростые (иными словами НОД(A, B) = 1) — то НОК(A, B) = A*B. Если же у этих чисел есть делители d0, d1, ..., dn, то их общими кратными будут числа: (A*B)/d0, (A*B)/d1, … (A*B)/dn. Значит, чтобы найти наименьшее общее кратное, нужно найти наибольший из делителей:

наименьшее_общее_кратное(a, b) {
  верни (A*B)/наибольший_общий_делитель(a, b);
}

Как найти НОД и НОК

Чтобы найти наименьшее общее кратное (НОК) и наибольший общий делитель (НОД) двух чисел воспользуйтесь нашим онлайн калькулятором:

Просто введите числа и получите результат.

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

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

См. также