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

      Комментарии к записи Ответ в теме: Наименьшее общее кратное последовательности чисел отключены
#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.