StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Easy.</p> <p>In pseudocode</p> <pre><code>a = b = floor(sqrt(N)) if (a * b >= N) return (a, b) a += 1 if (a * b >= N) return (a, b) return (a, b+1) </code></pre> <p>and it will always terminate, the distance between <code>a</code> and <code>b</code> at most only 1.</p> <p>It will be much harder if you relax second constraint, but that's another question.</p> <p>Edit: as it seems that the first condition is more important, you have to attack the problem a bit differently. You have to specify some method to measure the <em>badness</em> of not being square enough = 2nd condition, because even prime numbers can be factorized as <code>1*number</code>, and we fulfill the first condition. Assume we have a badness function (say <code>a >= b && a <= 2 * b</code>), then factorize <code>N</code> and try different combinations to find best one. If there aren't any good enough, try with <code>N+1</code> and so on.</p> <p>Edit2: after thinking a bit more I come with this solution, in Python:</p> <pre><code>from math import sqrt def isok(a, b): """accept difference of five - 2nd rule""" return a <= b + 5 def improve(a, b, N): """improve result: if a == b: (a+1)*(b-1) = a^2 - 1 < a*a otherwise (a - 1 >= b as a is always larger) (a+1)*(b-1) = a*b - a + b - 1 =< a*b On each iteration new a*b will be less, continue until we can, or 2nd condition is still met """ while (a+1) * (b-1) >= N and isok(a+1, b-1): a, b = a + 1, b - 1 return (a, b) def decomposite(N): a = int(sqrt(N)) b = a # N is square, result is ok if a * b >= N: return (a, b) a += 1 if a * b >= N: return improve(a, b, N) return improve(a, b+1, N) def test(N): (a, b) = decomposite(N) print "%d decomposed as %d * %d = %d" % (N, a, b, a*b) [test(x) for x in [99, 100, 101, 20, 21, 22, 23]] </code></pre> <p>which outputs</p> <pre><code>99 decomposed as 11 * 9 = 99 100 decomposed as 10 * 10 = 100 101 decomposed as 13 * 8 = 104 20 decomposed as 5 * 4 = 20 21 decomposed as 7 * 3 = 21 22 decomposed as 6 * 4 = 24 23 decomposed as 6 * 4 = 24 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload