好吧我的问题是数学的性质。 我有长度为X，我需要找到其相乘等于X的两个最接近的数字，我需要做到这一点，因为我是从一个字节数组，一个bulding的位图的字节数组，我需要做的位图的样子方尽可能多地。 我在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:
我重写了在有足够的意见和一些简单来说一个详细的功能由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 3:
请注意，如果X是在所有的大，然后从开方（X）开始，向下的工作一步一个脚印的时间将是一个悲惨的任务。 这可能要花费大量的时间。
如果你能找到然而数的因素，然后简单地计算是小于的sqrt（x）x的所有约数。
考虑数X = 123456789012345678901234567890.的最小整数比的sqrt少（X）是351364182882014，所以简单地递减该值来测试一个除数可以是有问题的。
保理X，我们得到的主要因素，这个名单：
{2, 3, 3, 3, 5, 7, 13, 31, 37, 211, 241, 2161, 3607, 3803, 2906161}
这是一个相当快的操作来计算除数小于开方（N）给出的首要因素，这将产生一个除数349788919693221，所以我们有
349788919693221 * 352946540218090 = 123456789012345678901234567890
这是最接近的对数N.但是，有多少次会，我们需要递减，开始的约数的平方根（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 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:
一种选择是建立优化问题
最小化的因素，X和Y的产品X×Y和P.你必须因此被加权一些两个物镜的目标函数的差的差：
min c × |X × Y - P| + d × |X – Y|
subject to X, Y ∈ ℤ
X, Y ≥ 0
其中c，d是定义你的价值，其目标有多少非负数。
像sqrt的解决方案却很多：）
Answer 6:
谢谢您的回答。 我已经提出，将查找最近3个整数建设上的sqrt方法的函数：
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
文章来源: Input an integer, find the two closest integers which, when multiplied, equal the input
