Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка.
Зная наибольший общий делитель (НОД) двух целых чисел m и n, их наименьшее общее кратное можно вычислить по такой формуле:
{\displaystyle{НОК(m, n)=\frac{m \cdot n}{НОД(m, n)}}}
Задача Найти наименьшее общее кратное двух чисел n1 и n2.
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
31
32
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
31
32
#include <iostream>
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 << "n1=";
cin >> n1;
cout << "n2=";
cin >> n2;
cout << NOK(n1, n2);
cin.get(); cin.get();
return 0;
}Результат выполнения
