Task 63. НОК - наименьшее общее кратное

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

Входные данные: дан массив натуральных чисел (рамез массива не больше 20), значения элементов массива не превышают 100.

Найти НОК заданных чисел.

Пример: 

[ 2, 3 ]

НОК = 6

Идея: так как значения чисел могут доходить до 100, а массив таких чисел размером до 20 элементов, то их НОК может выходить за пределы стандартного целочисленного типа. В этом случае можно воспользоваться длинной арифметикой.

Рассмотрим как можно вычислить НОК(k1, k2, ..., kn). Переберем все пары (ki, kj), где i < j, для каждой пары вычислим D = НОД(ki, kj), после чего разделим mj на D.

После этого произведение оставшихся mi равно значению НОК(m1, m2, ..., mn).

Для наглядности разберем конкретный пример,

НОК(2, 12, 6, 24, 3). 

В цикле переберем все пары (ki, kj), поделив kj на D.

1. После перебора пар (k1, kj) = (2, kj) массив будет содержать числа (2, 6, 3, 12, 3)

2. После перебора пар (k2, kj) = (6, kj) массив будет содержать числа (2, 6, 1, 2, 1)

3. После перебора пар (k3, kj) = (1, kj) массив будет содержать числа (2, 6, 1, 2, 1)

4. После перебора пар (k4, kj) = (2, kj) массив будет содержать числа (2, 6, 1, 2, 1)

По окончанию цикла вычисляем произведение всех чисел, содержащихся в массиве. Оно равно НОК(2, 12, 6, 24, 3) = 2 * 6 * 1 * 2 * 1 = 24

Реализация:

https://gist.github.com/unilecs/b6313f7042a6d785af302d2ec90a8c49

Тест:

https://dotnetfiddle.net/4LwZsz

Wiki:

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

НОД - Наибольший общий делитель