python - 将整数分解为尽可能接近平方的值

Question

我有一个函数可以逐字节读取文件并将其转换为 float 组。它还返回所述数组中的元素数。现在我想将数组 reshape 为二维数组，形状尽可能接近正方形。

例如让我们看一下数字 800:

sqrt(800) = 28.427...

现在我可以通过反复试验找出 25*32 将是我正在寻找的解决方案。如果整数相乘的结果很高，我会减少 sqrt(四舍五入到最接近的整数)，如果结果太低，我会增加它们。

我知道对素数执行此操作的算法，但这不是我的要求。我的问题是，即使我实现的蛮力方法有时也会卡住并且永远不会完成(这就是我任意限制迭代的原因):

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)

在输出上方使用此脚本将陷入循环打印

[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

但我想知道是否有更有效的解决方案？当然，我不可能是第一个想要做这样的事情的人。

Answer 1

def factor_int(n):
    val = math.ceil(math.sqrt(n))
    val2 = int(n/val)
    while val2 * val != float(n):
        val -= 1
        val2 = int(n/val)
    return val, val2, n

试试看:

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