# Algorithm to find $ab = N$ with $a$ and $b$ as close as possible

Given a number $N$ I would like to factor it as $N=ab$ where $a$ and $b$ are as close as possible; say when $|b-a|$ is minimal. For certain $N$ this is trivial: when $N$ is prime, a product of two primes, a perfect square, or one less than a perfect square, for example.

But in general it seems tricky. A lot of obvious first steps don't work. For example, it is tempting to guess that when $N=k^2M$, we can find $a_M\cdot b_M = M$, and the optimal solution for $N$ will be $ka_M\cdot kb_M$. But this is quite wrong; a counterexample is $N=20$. Are there any divide-and-conquer tactics of this sort that do work?

An obvious algorithm to find the optimal $a$ and $b$ might begin by calculating $s=\left\lfloor\sqrt N\right\rfloor$, which can be done efficiently, and then by working its way down from $s$ looking for a factor of $N$ by trial division, which is slow. Is there a more efficient algorithm?

It seems to me that even if the complete factorization of $N$ is known, partitioning the factors into two sets whose products are as close as possible will be NP-complete; it looks similar to the subset-sum problem, for example.

• By close, I assume $\vert b - a \vert$ is minimized?
– user17762
Jan 19, 2013 at 3:47
• I was not sure whether to minimize $|b-a|$ or $\left|\log \frac ba\right|$. But I think the same factorizations are optimal regardless of which metric one chooses. I have amended the question to commit to minimizing $|b-a|$.
– MJD
Jan 19, 2013 at 3:49
• Peripheral comment: I think I first began to consider this problem when I noticed that $7! = 70\cdot72$.
– MJD
Jan 19, 2013 at 3:54
• Varients of Fermat's factorization method would be more efficient then your algorithm Jan 19, 2013 at 3:54