We are given as input 2 integers $N$ and $q$. We have to express $N$ as a product of $q$ numbers, such that the maximum number among the $q$ numbers is minimized. The maximum value which $N$ can take is restricted to $10^9$.
Let $N = a_1 * a_2 * \cdots * a_{q-1} * a_q$, where all $a_i$'s are integers. We want the maximum among these $q$ numbers to be minimized.
I created a list of prime factorization of $N$. I tried using a greedy approach of taking the $2$ smallest numbers in each step and multiplying and including them in the factors list. But this gave a wrong answer for $N=512$ and $q=3$.
My algorithm returned $16*8*4$ while the correct answer is $8*8*8$. The maximum factor in the former is $16$, while in the latter is $8$.
I tried another approach of distributing the prime factors into $q$ boxes, which works for the above case, but fails for $N=12$ and $q=2$. We get the answer as $12=6*2$ instead of the optimal $12=3*4$.
I am stuck and don't know how to approach this problem.
Note if $N$ is a $q$-th root, then your problem is minimized by taking $$\underbrace{N^{\frac{1}{q}} \cdots N^{\frac{1}{q}}}_{q-\text{times}}.$$ Otherwise, consider $\lceil N^{\frac{1}{q}} \rceil$, and compute whether $\frac{N}{\lceil N^{\frac{1}{q}} \rceil}$ is an integer.
If not, try $\lceil N^{\frac{1}{q}} \rceil + 1$, and so on.