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

Алгоритмизация / Наименьшее общее кратное

 

Наименьшее общее кратное (НОК) двух целых чисел 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 <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;
}


Результат выполнения
Наименьшее общее кратное: результат выполнения


Назад: Алгоритмизация

Комментариев к записи: 8

  • int d должна выполняться на стадии сборки,поэтому лучше бы перенести ее к началу. если a*b превзойдет числа,которые может выдать int,то получится ошибка.Поэтому нужно поставить скобки.Вот так a*(b/NOD(a,b))

    • Елена Вставская
      Соглашусь, можно поставить скобки. Тем более, что b на NOD заведомо делится. Перенос int d зависит от выбранного компилятора. В Си все переменные должны быть объявлены в начале программы. C++ допускает объявление переменных в любом месте программы.


  • Это бредовая формула, т.к. для нахождения НОК, необходимо перемножать только отличающиеся множители чисел, а то, что в примере подобрали частный случай  ничего не доказывает. Вот пример НОК(12, 18) = 36, т.к. 36/12=3 и 36/18=2, а если верить коду, то: НОК(12,18)=216! Программа ищет некоторое число, которое делится на необходимые, а не НАИМЕНЬШЕЕ. 

    • Елена Вставская
      Неверно! Наименьшее общее кратное - это произведение чисел, деленное на их наибольший общий делитель.
      НОД(12,18) = 6.
      12*18 = 216
      Следовательно,
      НОК(12,18) = 12*18/НОД(12,18) = 216/6 = 36.

    • Исходя из формулы необходимо 12 умножить на 18 а затем разделить на НОД а он равен 6, соответственно и получается что НОК по формуле равен 36, все верно.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *