meetaig meetaig - 3 months ago 9
Python Question

Factor an integer to something as close to a square as possible

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.

As an example let's look at the number 800:

sqrt(800) = 28.427...


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

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):

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 > 10000):
if(result > 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)


using this script above the output will get stuck in a loop printing

[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


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.

Answer
def factor_int(n):
    nsqrt = math.ceil(math.sqrt(n))
    solution = False
    val = nsqrt
    while not solution:
        val2 = int(n/val)
        if val2 * val == float(n):
            solution = True
        else:
            val-=1
return val, val2, n

try it with:

for x in xrange(10, 20):
      print factor_int(x)