decomposition of a natural number Let's say we have natural numbers $n,k$. Is there an effective way to represent $k$ as $a_1\cdot\ldots\cdot a_n$ such that each $a_i$ is natural and the sum $a_1+\cdots +a_n$ is minimal?
It seems not so hard but I cannot figure it out. In case $n=2$ we only need to take the square root of $k$ and take $k=ab$, where $a$ is the greatest divisor of $k$ that $a\leq\sqrt{k}$ and $b$ is the smallest divisor of $k$ with $b\geq\sqrt{k}$.
But I cannot figure out the case when $n>2$.
 A: We have the condition $k={a_1a_2...a_n}$
Given $a_1, a_2, ... a_{n-1}$ we have $a_n=\frac k {a_1a_2...a_{n-1}}$
We want to minimise $A=a_1+ a_2+ ... +a_{n-1}+\frac k {a_1a_2...a_{n-1}}$
$\frac {\partial A}{\partial a_1}=1-\frac k {{a_1}^2a_2...a_{n-1}}$ 
For minimum $A$ we have $1-\frac k {{a_1}^2a_2...a_{n-1}}=0$
${{a_1}^2a_2...a_{n-1}}=k$
It can be shown that ${{a_i}^n}=k$ or $a_i=k^{\frac 1 n}$.
This gives the solution to the non-integer problem. The integer problem is harder.
For $n=2$ it is sufficient to find the largest divisor less than $\sqrt k$ because this is equivalent to finding the smallest divisor greater than $\sqrt k$. Think about the list of factors increasing from 1 to $k$: they are all in pairs (unless $\sqrt k$ is an integer).
For $n>2$ the problem becomes harder. My initial thoughts were:
1) Find the smallest divisor $b$ that satisfies $b=>\frac {k} {{k}^{\frac 1 n}}$.
2) Divide $k$ by $b$.
3) Reduce $n$ by 1 and repeat.
Other users posted comments about non-unique solutins, so I suggested the alternative:
1) Find the largest divisor $b$ that satisfies $b<={{k}^{\frac 1 n}}$.
2) Divide $k$ by $b$.
3) Reduce $n$ by 1 and repeat.
A combined approach was to try both and identify the better set.
BUT comments showed that this still did not give the correct solution in certain cases (eg $k=6300$).
So I have returned to think about this further.
Let $b_i=k^{\frac i n}$
In the non-integer situation we have $b_1=a_1$ and that $b_2=a_1a_2$ and that in general $b_i=a_1a_2...a_i$
In the integer problem we want $a_1a_2...a_i$ to be as close to $b_i$ as possible.
So for each $b_i$ find the lowest divisor of $k$ that is larger than $b_i$ and the largest divisor of $k$ that is smaller than $b_i$. This gives us a total of $2(n-1)$ possible divisors of $k$. We will need to investigate each one of these divisors in turn:
Suppose we have chosen to investigate the divisor $d_i$ which is close to $b_i$ (either above or below). We must consider the possible separations of $d_i$ into $a_1a_2...a_i$ and the possible separations of $\frac k {d_i}$ into $a_{i+1}a_{i+2}...a_n$. Use the same approach as for k.
How long will this take?
There are $2(n-1)$ possible divisors to consider in the first step.
Each of these yields a further $2(n-2)$ possible divisors in the second step. There will be some overlap with the divisors identified in the first step, but we cannot assume this will happen. It might be possible to build into an algorithm the ability to check for already attempted divisors.
In the third step there will be $2(n-3)$ possible divisors.
So the total possible sets to investigate are $2(n-1) \times 2(n-2) \times 2(n-3) \times ... \times 2=2^{n-1} {(n-1)}!$ 
