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

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

Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка.
Зная наибольший общий делитель (НОД) двух целых чисел m и n, их наименьшее общее кратное можно вычислить по такой формуле:

НОК = m * n / НОД (m, n)

Реализация

#include <iostream>
using namespace std;
int NOD(int n1, int n2) { ... }
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;
}

Результат выполнения

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

Назад


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

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

  • Это бредовая формула, т.к. для нахождения НОК, необходимо перемножать только отличающиеся множители чисел, а то, что в примере подобрали частный случай  ничего не доказывает. Вот пример НОК(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.


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

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