Let us examine one arbitrary prime, $X$. How many times can you divide the sequence with $X$? Obviously, the smallest number of times you can divide each number in sequence with $X$. Suppose we know for each number in sequence number $b_i$ which indicates the number of times we can divide the $i^{\text{th}}$ number in the sequence by $X$. Dividing one number with $X$ and multiplying some other number with $X$ now turns into decreasing/increasing corresponding $b$'s. Since our goal is to maximize the smallest $b$, it's quite obvious that the best thing to do is always take one away from the largest $b$ and add it to the smallest, until all $b$'s are equal or almost equal (they can be off by at most one). It can be easily seen now that the solution for each $X$ is equal to the sum of all $b$'s for the corresponding $X$ divided by the number of elements, rounded down.

Using the sieve of Eratosthenes for fast prime number generation solves this task under given constraints.