Factor an integer to something as close to a square as possible
<p>I have a function that reads a file byte by byte and converts it to a floating point array. It also returns the number of elements in said array.
Now I want to reshape the array into a 2D array with the shape being as close to a square as possible.</p>

<p>As an example let's look at the number 800:</p>

<p><code>sqrt(800) = 28.427...</code></p>

<p>Now by I can figure out by trial and error that <code>25*32</code> would be the solution I am looking for. 
I do this by decrementing the <code>sqrt</code> (rounded to nearest integer) if the result of multiplying the integers is to high, or incrementing them if the result is too low.</p>

<p>I know about algorithms that do this for primes, but this is not a requirement for me. My problem is that even the brute force method I implemented will sometimes get stuck and never finish (which is the reason for my arbitrary limit of iterations):</p>

<pre><code>import math

def factor_int(n):
    nsqrt = math.ceil(math.sqrt(n))

    factors = [nsqrt, nsqrt]
    cd = 0
    result = factors[0] * factors[1]
    ii = 0
    while (result != n or ii &gt; 10000):
        if(result &gt; n):
            factors[cd] -= 1
        else:
            factors[cd] += 1
        result = factors[0] * factors[1]
        print factors, result
        cd = 1 - cd
        ii += 1

    return "resulting factors: {0}".format(factors)

input = 80000
factors = factor_int(input)
</code></pre>

<p>using this script above the output will get stuck in a loop printing</p>

<pre><code>[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
[274.0, 292.0] 80008.0
[273.0, 292.0] 79716.0
[273.0, 293.0] 79989.0
[274.0, 293.0] 80282.0
</code></pre>

<p>But I wonder if there are more efficient solutions for this? Certainly I can't be the first to want to do something like this.</p>

<p>Interesting question, here's a possible solution to your problem:</p>

<pre><code>import math


def min_dist(a, b):
    dist = []
    for Pa in a:
        for Pb in b:
            d = math.sqrt(
                math.pow(Pa[0] - Pb[0], 2) + math.pow(Pa[1] - Pb[1], 2))
            dist.append([d, Pa])

    return sorted(dist, key=lambda x: x[0])


def get_factors(N):
    if N &lt; 1:
        return N

    N2 = N / 2
    NN = math.sqrt(N)

    result = []
    for a in range(1, N2 + 1):
        for b in range(1, N2 + 1):
            if N == (a * b):
                result.append([a, b])

    result = min_dist(result, [[NN, NN]])
    if result:
        return result[0][1]
    else:
        return [N, 1]


for i in range(801):
    print i, get_factors(i)
</code></pre>

<p>The key of this method is finding the minimum distance to the cartesian point of [math.sqrt(N), math.sqrt(N)] which meets the requirements N=a*b, a&amp;b integers.</p>

python algorithm cython factoring