There is currently no known polynomial time algorithm for finding prime factorizations of integers, so here is an algorithm which, while far from perfect, still runs in polynomial time.
Let $A=\{a_1,\ldots,a_k\}$, let $M$ be the maximum element of $A$, and let $n=\log_2{M}$. We will determine the computational complexity in terms of $n$ and $k$.
Every prime $p$ has a largest power $m_p$ amongst elements of $A$, which is to say $m_p$ is the power of $p$ in $\text{lcm}\hspace{1pt}A$. Our first goal will be to find values $b_i$, which will be a multiple of only those primes $p$ for which the power of $p$ in $a_i$ is $m_p$. We will then use these to find values $c_i$, which will be the product of values $p^{m_p}$ such that $p^{m_p}$ divides $a_i$. Finally, we will consider these against each other to determine $n_i$. This will be completed in $\mathcal{O}(k\cdot n^5+k^2\cdot n)$ time, which is indeed a polynomial.
For each $a_i$, we define
$$b_i=\frac{a_i^{n+1}}{\gcd(a_i^{n+1},\text{lcm}\hspace{1pt}\{a_j^n\text{ s.t. }j\neq i\}\})}$$
Let us figure out what is happening here. What the denominator does is find the the maximum power of every prime which divides an element of $A\backslash\{a_i\}$, and multiplies that maximum by $n$. It then takes these powers and compares them with those found in $a_i^{n+1}$, and takes the smaller one. If the power of $p$ found in $a_i$ is $p^{m_p}$, where $m_p$ must be at most $n$, then $p^{m_p}\cdot(n+1)>p^{m_p}\cdot n$, so $p$ will divide $b_i$, and otherwise, since $(p^{m_p}-1)\cdot(n+1)<p^{m_p}\cdot n$, $p$ will not divide $b_i$. Thus $p$ divides $b_i$ if and only if $p^{m_p}$ divides $a_i$. This process will take $\mathcal{O}(k\cdot n^4)$ time, resulting from taking $k$ $\gcd$ functions on values with at most about $n^2$ bits.
Now we wish to find $c_i$, for which the power of $p$ is $m_p$ if $p^{m_p}$ divides $a_i$ and 0 otherwise. To do this, we will do the following (note the subscripts have been removed here for clarity):
x = gcd(a,b)
while (x != 1)
c *= x
a /= x
x = gcd(a,b)
Every iteration, this will multiply the power of $p$ in $c_i$ by at least 1 so long as it is not yet $p^{m_p}$. Thus it will take at most $m_p\leq n$ iterations, each taking $\mathcal{O}(n^5)$ time due to the multiplication, so the process of finding values of $c_i$ takes at most $\mathcal{O}(k\cdot n^5)$ time.
Finally, we need to find our values of $n_i$. We find these in order. We simply let $n_1=c_1$, then take the $\gcd$ of this with the other values of $c_i$ and divide these old values of $c_i$ by that $\gcd$ to get new values. We then do this with every other value from 2 to $k$, taking $\mathcal{O}(k^2\cdot n+n^2)$ time, giving us working values of $n_i$ in polynomial time.
Best Answer
Another very specific trick, based on the multiple choices: since all the choices are of the form $\displaystyle \frac{n-1}{n} = 1 - \frac{1}{n}$, you're trying to find $n$ for which $1/n$ is closest to 1−(your fraction). So you'd consider (denominator−numerator)/denominator = (3186−2860)/3186 which is (around 320)/3186, clearly closest to 1/10.