Наименьшее общее кратное
Материал из Циклопедии
Наименьшее общее кратное (НОК) — это наименьшее натуральное число для двух заданных натуральных чисел, кратное этим числам.
[править] Обозначения
Введём обозначения:
a — первое натуральное число;
b — второе натуральное число;
n — наименьшее общее кратное чисел a и b, обозначается НОК(a, b).
[править] Алгоритм НОК
Входные данные: a; b.
- c = a; d = b
- Если c > d, то c = c − d.
- Если c < d, то d = d − c.
- Если c > d, то идти к 2.
- n = ab/c
Выходные данные: n.
- Заметим, что НОК(a, b)=ab/НОД(a, b)
[править] Другие алгоритмы
- наибольший общий делитель;
- наименьшее общее кратное;
- проверка кратности;
- деление по модулю;
- решето Эратосфена;
- разложение числа на множители;
- система счисления;
- метод математической индукции;
- схема примитивной рекурсии;
- виды рекурсии;
- машина Поста;
- машина Тьюринга (вероятностная);
- комбинаторные алгоритмы;
- сортировка;
- алгоритм определения мест.