Ответ в теме: Наименьшее общее кратное последовательности чисел

      Комментарии к записи Ответ в теме: Наименьшее общее кратное последовательности чисел отключены
#2583

Я думаю, что решение через НОД тоже может работать (надо проверить), но если нужно обойтись без него – то наименьшее общее кратное – это такое число LCD = k*max(List), что для любого элемента E из списка List выполняется LCD mod E = 0, при этом k = 1, 2, ... (должно быть минимальным). Такая формула связана с тем, что НОК не может быть меньше max(List), т.к. тогда оно не сможет быть кратно максимуму. С другой стороны – числа, кратные max(List)можно описать как k*max(List), где k – целое число. Отсюда может быть получен следующий алгоритм:

  1. вычислить Increment = max(List), V = Increment;
  2. если для любого элемента E списка List выполняется V mod E = 0 – вернуть V;
  3. V = V + Increment;
  4. переход на п. 2.