arrays - 输入一个整数，找到两个最接近的整数，当它们相乘时，等于输入

Question

好的，我的问题是数学性质的。我有一个长度为 X 的字节数组，我需要找到两个最接近的数字相乘等于 X。我需要这样做，因为我正在从字节数组中生成位图，我需要使位图看起来像尽可能一个正方形。我用 C# 编写代码，但不用担心语法，任何算法或伪代码都可以。在此先感谢您的帮助

Answer 1

对此可能有更好的算法，但在我的脑海中：

1) Take the square root of the number X; we'll call it N.
2) Set N equal to the ceiling of N (round up to the nearest integer).
3) Test for (X % N). If N divides evenly into X, we found our first number.
  if 0, divide X by N to get M. M and N are our numbers
  if not 0, increment N by 1 and start step 3 over.

Answer 2

请注意，如果 X 很大，那么从 sqrt(X) 开始并一次向下工作将是一项痛苦的任务。这可能需要大量时间。

但是，如果您可以找到数字的因数，则只需计算 X 的所有小于 sqrt(X) 的除数。

考虑数字 X = 123456789012345678901234567890。小于 sqrt(X) 的最小整数是 351364182882014，因此简单地减小该值以测试除数可能会有问题。

分解 X，我们得到这个素因子列表：

{2, 3, 3, 3, 5, 7, 13, 31, 37, 211, 241, 2161, 3607, 3803, 2906161}

给定主要因素，计算小于 sqrt(N) 的除数是一个相当快的操作，得到除数 349788919693221，所以我们有

349788919693221 * 352946540218090 = 123456789012345678901234567890

这些是数字 N 的最接近的一对除数。但是，从 sqrt(N) 开始，我们需要递减多少次？这个区别是：1575263188793，所以超过 1.5e12 步。

确定指示因素的简单方案（在 MATLAB 中）

Dmax = 351364182882014;
F = [2, 3, 3, 3, 5, 7, 13, 31, 37, 211, 241, 2161, 3607, 3803, 2906161];
D = 1;
for i = 1:numel(F)
  D = kron(D,[1,F(i)]);
  D = unique(D);
  D(D > Dmax) = [];
end

D(end)
ans =
     349788919693221

另一个因素是足够简单地获得的。如果数字太大而无法超过双精度燧石的动态范围，那么您将需要使用一些更高精度的算术变体。

Answer 3

我已经用详细的函数重写了 user85109 上面提出的 MATLAB 答案，并带有足够的注释和一些更简单的术语。当然非常有效，适用于大量数字，并且希望很容易用任何提供库函数来获取整数的素数分解的语言编写。

        function [a, b] =  findIntegerFactorsCloseToSquarRoot(n)
        % a cannot be greater than the square root of n
        % b cannot be smaller than the square root of n
        % we get the maximum allowed value of a
        amax = floor(sqrt(n));
        if 0 == rem(n, amax)
            % special case where n is a square number
            a = amax;
            b = n / a;
            return;
        end
        % Get its prime factors of n
        primeFactors  = factor(n);
        % Start with a factor 1 in the list of candidates for a
        candidates = [1];
        for i=1:numel(primeFactors)
            % get the next prime factr
            f = primeFactors(i);
            % Add new candidates which are obtained by multiplying
            % existing candidates with the new prime factor f
            % Set union ensures that duplicate candidates are removed
            candidates  = union(candidates, f .* candidates);
            % throw out candidates which are larger than amax
            candidates(candidates > amax) = [];
        end
        % Take the largest factor in the list d
        a = candidates(end);
        b = n / a;
    end

Answer 4

一个完美的正方形应该有 SQRT(X) 的一边，所以从那里开始向下工作。

int X = ...
for(int i=sqrt(x);i>0;i--) {
  // integer division discarding remainder:
  int j = X/i;
  if( j*i == X ) {
    // closest pair is (i,j)
    return (i,j);
  }
}
return NULL;

请注意，这仅在X实际上可被两个整数整除时才有效（即素数X将以 结束(1,X)）。根据你在做什么，你最好选择稍微大一点的尺寸，然后把它做成方形......即有边CEILING(SQRT(X))。

Answer 5

我还不允许发表评论，所以这里是一个快速的 python>=3.8 实现，基于@Anthony DeSimone 的答案修改为使用 floor() 正如@Egor Skriptunoff 建议的那样：

import math
def sqrt_int(X: int):
    N = math.floor(math.sqrt(X))
    while bool(X % N):
        N -= 1
    M = X // N
    return M, N

Answer 6

一种替代方法是设置此优化问题

最小化因子 X 和 Y 的差异乘积 X × Y 和 P 的差异。因此，您有一个目标函数，它是两个目标中的一些加权：

       min c × |X × Y - P|  +  d × |X – Y|
subject to X, Y ∈ ℤ
           X, Y ≥ 0

其中 c, d 是非负数，用于定义您重视哪个目标。

但是非常喜欢这个sqrt解决方案:)

Answer 7

这个答案（在 python3 中）是从 Shailesh Kumar 借来的，它本身是从 user85109 借来的。

先前的两个答案都未能解决素因子​​的低自倍数，这意味着值（低于 100），例如 [18, 22, 26, 34, 38, 46, 58, 62, 66, 68, 70, 74, 76 , 78, 82, 84, 86, 87, 92, 93, 94, 96, 98] 失败。

以下解决了这个问题，并且对于大量数据来说足够快。我还在构建候选者时使用了集合结构，因为集合“免费”提供唯一性，最终转换和排序的成本（较低）。

因为候选包括不将n整除的因素，所以我们必须最终确保满足条件。

import math
from sympy.ntheory import primefactors


def int_root(n: int) -> tuple:
    root_n = math.sqrt(n)
    if 0 == n % root_n:
        a = int(root_n)
        return a, n // a
    pfs = primefactors(n)
    candidates = {1}
    for pf in pfs:
        for fi in range(math.ceil(math.log(root_n, pf))):
            candidates = candidates | {pf * c for c in candidates if pf * c < root_n}
    candidates = {c for c in candidates if n / c == n // c}
    a = max(candidates)
    return a, n / a


if __name__ == '__main__':
    for i in [18, 22, 26, 34, 38, 46, 58, 62, 66, 68, 70, 74, 76, 78, 82, 84, 86, 87, 92, 93, 94, 96, 98]:
        r = int_root(i)
        print(i, r)

Answer 8

感谢您的回答。我制作了一个函数，可以在 sqrt 方法上找到最接近的 3 个整数：

function [a, b, c] =  findIntegerFactorsCloseToCubeRoot(n)
% a cannot be greater than the cube root of n
% b cannot be smaller than the cube root of n
% we get the maximum allowed value of a
amax = floor(nthroot(n,3))
if amax^3 == n
    % special case where n is a cube number
    a = amax;
    b = a;
    c = a;
    return;
end
% Get its prime factors of n
primeFactors  = factor(n);
% Start with a factor 1 in the list of candidates for a
candidates = [1];
for i=1:numel(primeFactors)
    % get the next prime factor
    f = primeFactors(i);
    % Add new candidates which are obtained by multiplying
    % existing candidates with the new prime factor f
    % Set union ensures that duplicate candidates are removed
    candidates  = union(candidates, f .* candidates);
    % throw out candidates which are larger than amax
    candidates(candidates > amax) = [];
end
% Take the largest factor in the list d
a = candidates(end);
% call similar function for remaining 2 factors
[b, c] = findIntegerFactorsCloseToSqRoot(n/a);
end