How to find a number that will be divisible without a remainder by all elements of an array?

Question

Algorithms

Hello everybody!
There is an array of integers (unsigned long), for example 1, 3, 5, 5, 3, 13, 300, 100, 11, 33128, 65789, 100 ...
How to find the maximum number for unsigned long that is divisible by these numbers?

Answer 1

1. $x = Multiply elements from array_unique($array);
2. $k = floor(4294967296 / $x);
3. $x * $k;
Write the code for this algorithm yourself?
upd: The truth will only work if the product is less than max :)

Answer 2

I would first sort the array of numbers in ascending order.
Why would I check for each element of the array if there is a number in the array greater than the given one (for this, I sorted the array so as not to go through all the elements of the array each time - this saves time), which is divisible by the given one, and if there is such a number, then the current we throw it away, since it is already part of a larger number.
(For example, in the above array there is the number 3 and there is the number 300, 3 can be thrown out, because 300 is divisible by 3.)
Why do we multiply the remaining numbers (excluding duplicates, if any).
(this will reduce the number of numbers and thus avoid overflow of unsigned long type on long arrays)
If this option does not work, and it is possible (for example, a very long array), then there is a more complicated option:
We represent each element of the array as a product of prime numbers
and add all unique prime numbers to a dictionary, where the key is a prime number, and the value is the maximum the degree to which the given prime number is included in the elements of the original array.
For example: there is a number 100500 = 2*2*3*5*5*5*67, then the dictionary will be like this
{2: 2, 3: 1, 5: 3, 67:1}
After iterating through all the elements of the original array, we will have a dictionary prime numbers and their maximum powers.
To get the result, we take and multiply all the keys of the dictionary raised to the power of the value of the corresponding of the keys, this will give the smallest number that is divisible by all elements of the original array.

Answer 3

We take the NOC. When calculating the LCM, an overflow occurred ((a b) div b ≠ a) → no such overflow.
Next (MAX_UNSIGNED_LONG div LCM) LCM.
UPD. Put a new code for detecting overflows when multiplying; the old one is clearly wrong: 11 11 = 121, and with two decimal places it will be 21 > 11.
UPD2. Do you know how overflow-resistant LCM is considered? LCM(x,y) = (x div GCM(x,y)) * y

Answer 4

GCD for a pair of numbers is found using the Euclid algorithm or similar. LCM(a,b) = a*b*/gcd(a,b).
For massim just need to roll with this function.