# Finding three factors of a number with minimal sum

Suppose that we have a number $x \in \mathbb{Z}^+$.

I am seeking an algorithm to find three numbers $a, b, c \in \mathbb{Z}^+$ such that $a \times b \times c = x$ and $a + b + c$ is minimum.

Is this problem a variant of subset sum? Am I stuck with an exponential time algorithm?

## Examples

$32 = 4 \times 4 \times 2$
$36 = 4 \times 3 \times 3$
$11 = 11 \times 1 \times 1$
$6 = 2 \times 3 \times 1$

• – Mark Dominus Dec 12 '14 at 17:59

The first step is to find the prime factorization of $x$, which can be done with the general number field sieve.
Next, enumerate all possible values of $a,b$ and for each tuple $(a,b)$ compute $c$ to find the triple with the minumum sum. A number $x$ has at most $\exp(O(\log x / \log \log x))$ divisors, so there are also at most $\exp(O(\log x / \log \log x))$ such tuples.