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

Наименьшее общее кратное // KhanAcademyRussian [4:52]

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

Обозначения

Введём обозначения:

a — первое натуральное число;

b — второе натуральное число;

n — наименьшее общее кратное чисел a и b, обозначается НОК(a, b).

Алгоритм НОК

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

Входные данные: a; b.

1. c = a; d = b
2. Если c > d, то c = c − d.
3. Если c < d, то d = d − c.
4. Если c > d, то идти к 2.
5. n = ab/c

Выходные данные: n.

• Заметим, что НОК(a, b)=ab/НОД(a, b)

Другие алгоритмы

• наибольший общий делитель;
• наименьшее общее кратное;
• проверка кратности;
• деление по модулю;
• решето Эратосфена;
• разложение числа на множители;
• система счисления;
• метод математической индукции;
• схема примитивной рекурсии;
• виды рекурсии;
• машина Поста;
• машина Тьюринга (вероятностная);
• комбинаторные алгоритмы;
• сортировка;
• алгоритм определения мест.