将整数分解为尽可能接近正方形的东西 [英] Factor an integer to something as close to a square as possible

问题描述

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

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.

作为示例，让我们看一下数字800：

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

sqrt（800）= 28.427 ...

现在，通过反复试验，我可以找到 25 * 32 是我想要的解决方案。
我这样做是通过将 sqrt 递减（四舍五入为最接近的整数）（如果将整数相乘的结果为高），或者如果结果太低则将其递增

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.

推荐答案

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

尝试使用：

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

这篇关于将整数分解为尽可能接近正方形的东西的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！