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.