Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка.
Зная наибольший общий делитель (НОД) двух целых чисел m и n, их наименьшее общее кратное можно вычислить по такой формуле:
НОК = m * n / НОД (m, n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include
using namespace std;
// Наибольший общий делитель
int NOD( int n1, int n2)
int div;
if (n1 == n2) return n1;
int d = n1 — n2;
if (d < 0) d = -d; div = NOD(n1, d);
> else
div = NOD(n2, d);
return div;
>
// Наименьшее общее кратное
int NOK( int n1, int n2)
<
return n1*n2 / NOD(n1, n2);
>
int main()
int n1, n2;
cout cin >> n1;
Наименьшее общее кратное. 5 класс.
cout cin >> n2;
cout cin.get(); cin.get();
return 0;
>
Результат выполнения
Комментариев к записи: 8
Источник: prog-cpp.ru
НОК и НОД (исходный код)
Наименьшим общим кратным (НОК) двух целых чисел является наименьшее натуральное число, которое делится на эти два числа без остатка.
Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей.
Для нахождения наибольшего общего делителя (НОД) можно использовать алгоритм Евклида (способ «взаимного вычитания»). Наименьшее общие кратное, если извесен НОД чисел a и b, можно найти с помощью формулы: МОДУЛЬ(a * b)/НОД.
Ниже представлены реализации алгоритмов поиска НОК и НОД на разных языках программирования.
Для удобства можно скачать все исходные файлы в архиве кликнув по кнопке:
А посчитать НОК и НОД двух чисел вы можете прямо сейчас, перейдя по ссылке: НОК и НОД Онлайн.
Реализация на C (Си)
#include #include int NOD(int a, int b) < while (a != b)< if (a >b) < a -= b; >else < b -= a; >> return a; > int NOK(int a, int b) < return abs(a * b)/NOD(a, b); >int main()
Реализация на C++
#include #include using namespace std; int NOD(int a, int b) < while (a != b)< if (a >b) < a -= b; >else < b -= a; >> return a; > int NOK(int a, int b) < return abs(a * b)/NOD(a, b); >int main()< int a, b; cout > a >> b; cout $b) < $a -= $b; >else < $b -= $a; >> return $a; > function NOK($a, $b) < return abs($a * $b)/NOD($a, $b); >$a = $_GET[‘a’]; $b = $_GET[‘b’]; echo ‘NOK: ‘. NOK($a, $b) .’
ЧТО ТАКОЕ НОК И НОД? ЧАСТЬ I #математика #shorts #задачиегэ #профильныйегэ #нок #нод
‘; echo ‘NOD: ‘. NOD($a, $b); ?>
Реализация на JavaScript
function NOD(a, b) < while (a != b)< if (a >b) < a -= b; >else < b -= a; >> return (a); > function NOK(a, b) < return (Math.abs(a * b)/NOD(a, b)); >var a = Number(prompt(«Enter A:»)); var b = Number(prompt(«Enter B:»)); alert (‘NOK: ‘ + NOK(a, b)); alert (‘NOD: ‘ + NOD(a, b));
Источник: xn--90aihhxfgb.xn--p1ai
Наименьшее общее кратное пар чисел
Найти наименьшее общее кратное (НОК) пар целых положительных чисел через наибольший общий делитель (НОД) по формуле lcm = ab / gcd(a; b), где lcm — НОК, gcd — НОД, a и b — числа.
В основной ветке программы запрашиваются два числа, которые передаются в функцию, вычисляющую и возвращающую НОК.
В самой функции переменная, которой присваивается произведение переданных значений, имеет тип longint, т.к. диапазона ни integer, ни даже word может быть недостаточно.
Произведение следует найти до того, как будет найден НОД, т.к. в процессе его вычисления значения переменных-чисел уменьшается. НОД содержится в одной переменной-числе, но поскольку вторая в любом случае содержит 0, и мы не знаем, какая что именно содержит, то проще их сложить.
Программа на языке Паскаль:
var a, b: word; function lcm(c, d: word): word; var mult: longint; begin mult := c * d; while (c <> 0) and (d <> 0) do if c > d then c := c mod d else d := d mod c; lcm := mult div (c + d); end; begin repeat write(‘Two numbers: ‘); readln(a,b); if (a = 0) and (b = 0) then break; writeln(‘LCM: ‘, lcm(a,b)); until (a = 0) and (b = 0); end.
Пример выполнения программы:
Two numbers: 800 899 LCM: 63840 Two numbers: 15 16 LCM: 240 Two numbers: 121 212 LCM: 25652 Two numbers: 25 30 LCM: 150 Two numbers: 0 0
Источник: pas1.ru