将一个整数乘以一个尽可能接近平方的值

Question

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

作为一个例子，让我们看看数字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)

使用上面的脚本，输出将陷入循环打印

^{pr2}$

但我想知道是否有更有效的解决办法？当然，我不是第一个想做这种事的人。在

Answer 1

我认为模运算符很适合这个问题：

import math 

def factint(n):
    pos_n = abs(n)
    max_candidate = int(math.sqrt(pos_n))
    for candidate in xrange(max_candidate, 0, -1):
        if pos_n % candidate == 0:
            break
    return candidate, n / candidate

Answer 2

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

试试看：

^{pr2}$

Answer 3

有趣的问题，这里有一个可能的解决方案：

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

该方法的关键是求出到笛卡尔点的最小距离[数学硕士（N） 你说，数学硕士（N） ]满足要求N=a*b，a&b整数。在