Как найти число которое будет делиться без остатка на все элементы массива?

Question

[Александр Булитеров]

Всем Здравствуйте!

Есть массив целых чисел (unsigned long), например 1, 3, 5, 5, 3, 13, 300, 100, 11, 33128, 65789, 100 ...
Как найти максимальное число для unsigned long, которое делится без остатка на эти числа?

Comments

[Lynn «Кофеман»]

Точно максимальное, а не минимальное?

[Александр Булитеров]

Вот в том то и соль) что максимальное.

[Lynn «Кофеман»]

Ну, найти НОК, поделить на него maxint, взять целую часть и помножить обратно на НОК

Answer 1

[Lander]

1. $x = Перемножить элементы из array_unique($array);
2. $k = floor(4294967296 / $x);
3. $x * $k;
Код по этому алгоритму сами напишите?

upd: Правда сработает только если произведение меньше махint :)

Comments

[Lynn «Кофеман»]

Лучше, но неверно. Надо не перемножать все уникальные, а искать НОК

[Lander]

Алексей Тен, Да, я уже прочитал ваш комментарий под вопросом. Просто решил предложить альтернативное решение раз именно НАИМЕНЬШИЙ делитель не нужен.

[Lynn «Кофеман»]

Lander, проблема в том, что ваше решение может не найти правильный ответ.

Простой пример: пусть максимальное целое это 127 и массив из двух элементов [2, 40].
Ваш алгоритм выдаст 80, а правильный ответ 120.

Поэтому и нужен НОК

Answer 2

[Руслан .]

Я бы вначале отсортировал массив чисел по возрастанию.

Зачем для каждого элемента массива проверил бы, а нет ли в массиве числа большего чем данное (для этого сортировал массив, чтобы не перебирать каждый раз все элементы массива - это экономит время), которое делиться на данное, и если такое число есть, то текущее выбрасываем, т. к. оно уже входит в состав большего числа.
(Например в приведенном массиве есть число 3 и есть число 300, 3 можно выкинуть, т.к. 300 делится на 3.)

Зачем оставшиеся числа перемножаем (исключая дубли, если они будут).
(это позволит уменьшить количество чисел и тем самым избежать переполнения типа unsigned long на длинных массивах)

Если такой вариант не сработает, а это возможно (например очень длинный массив), то есть вариант посложнее:
Каждый элемент массива представляем как произведение простых чисел
и все уникальные простые числа складываем в словарь, где ключ - это простое число, а значение - это максимальная степень в которой данное простое число входит в элементы исходного массива.

Например: есть число 100500 = 2*2*3*5*5*5*67, тогда словарь будет такой
{2: 2, 3: 1, 5: 3, 67:1}

После перебора всех элементов исходного массива будем иметь словарь простых чисел и их максимальных степеней.
Для получения результата берем и перемножаем все ключи словаря возведенные в степень значения соответствующего из ключей, это даст наименьшее число, которое делиться на все элементы исходного массива.

Answer 3

[Mercury13]

Берём НОК. При расчёте НОКа случилось переполнение ((a · b) div b ≠ a) → нет такого.
Дальше (MAX_UNSIGNED_LONG div НОК) · НОК.

UPD. Поставил новый код обнаружения переполнений при умножении; старый явно ошибочный: 11·11 = 121, и при двух десятичных знаках будет 21 > 11.
UPD2. В курсе, как считают переполнение-устойчивый НОК? НОК(x,y) = (x div НОД(x,y)) * y

Answer 4

[Михаил Потанин]

НОД для пары чисел это находится с помощью алгоритма Евклида или похожего на него. НОК(a,b) = a*b*/НОД(a,b).
Для массима просто надо свернуть с этой функцией.