Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given $xy=C$ where $x, y$ are integer variables and $C$ is integer constant.

What is the most efficient algorithm that finds $x,y$ such that $x+y$ is minimum?

Providing references is highly appreciated.

Edit: Input integers are reasonably encoded.

share|cite|improve this question
Isn't this just a constrained optimization problem, restricted to integer solutions? Of course, one first needs to figure out what integers x and y multiply to C, which is the same as factoring C... – Aaron Mazel-Gee Nov 9 '10 at 7:57
@Aaron, yes, factorization is a special case. I'm interested in references to geometric approaches. – Mohammad Al-Turkistany Nov 9 '10 at 8:05
This is just the question of finding the factors of $C$ nearest the square root of $C$. In general factorizing an is hard. One special case where a "geometric" approach might be useful is when $C$ factors into a lot of small primes which you know. Then the problem reduces to finding integer values of $a_i$ in certain ranges making $\sum_i a_i\log p_i$ as close as possible to $(1/2)\log C$. This is finding which of a bunch of points is closest to a hyperplane. Americo, that's the maximum! Look at say $C=100$. Then $1+100 > 10+10$. – Robin Chapman Nov 9 '10 at 10:13
Robin Chapman: That's right! My big mistake. – Américo Tavares Nov 9 '10 at 23:21
... as you wrote above "That is just the question of finding the factors of $C$ nearest the square root of $C$." – Américo Tavares Nov 9 '10 at 23:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.