Factorizing n in given number of factors such that value of maximum factor is minimized

Question

Say I have 12 and have to factorize it in 2 factors. Now possible factors are
1, 12
2, 6
3, 4

Now 3,4 is such that value of maximum factor i.e. 4 is minimized among all pairs.

How to find the solution in generic case where a number N is to be divided in K factors minimizing maximum value.

Answer 1

You want your factors to be as close as possible to $N^{1/K}$. For your example of $12348000=2^5×3^2×5^3×7^3$ split into $3$ factors, we have $12348000^{1/3}\approx 231$. The smallest factor above $231$ is $240$, so we can start there. $\frac {12348000}{240}=51450=210\cdot 245$, so our desired factorization is $210\cdot 240 \cdot 245$. This is clearly the best possible because $240$ and $245$ are the factors just above the cube root. For other numbers you may have to hunt around more because the factors near the cube root contain the same prime factor and interfere with each other. Here you might be tempted to see the $5^3 \cdot 7^3$ and put $35$ into each factor. This would result in $210 \cdot 210 \cdot 280$, which is inferior. It gets harder as $K$ and the number of prime factors of $N$ get larger as there are more possibilities to check. If there are a couple large primes you can start by putting one into each factor then doing the best you can with the small ones to even things out.

Added: a recursive program could look something like this:
Input is $N, K$
Factor $N$ into prime factors
List all the factors of $N$ in increasing order
Compute $N^{1/K}$
Find the factor equal to or just above $N^{1/K}$. Call it $f$ Call the same routine with $N/f, K-1$ If the minmax factor returned is less than or equal to $f$ we are done. Return $f$ as the minmax factor. Else increase $f$ to the next larger factor and repeat.

Answer 2

This problem will (likely) not yield to an efficient general algorithm:

This problem can be reframed as a bin-packing problem. Perhaps the most usual bin-packing problem statement is: Given some items with various volumes, and an unlimited supply of bins, each with the same capacity (volume) $C$, what is the fewest number of bins needed to pack the items?

The given problem is a bit different. We know how many bins we are allowed, and we want to find the minimum (standard) bin capacity so that we can pack into the allotted number of bins of that size. However the second problem can be converted into the first by guessing at a solution (bin capacity) and seeing whether we can do our packing into the allowed number of bins of the guessed size. If so, we can reduce the guessed capacity and see if we can solve for the smaller bin size; if not, we can increase the guessed size.

Of course the given problem is multiplicative, and the bin-packing problem is additive. However, by taking logarithms of prime factors, we can convert the given problem into an additive bin-packing problem.

It is known that the bin-packing problem is NP-hard (find the minimum number of bins of a given capacity needed pack all the items); the corresponding decision problem (can we fit our items into a given number of bins of the specified size) is NP-complete. (See https://en.wikipedia.org/wiki/Bin_packing_problem)