整数的因式分解 [英] Factorization of an integer
问题描述
在回答另一个问题时,我迷迷糊糊地问了一个问题:我如何才能真正找到所有没有符号数学工具箱的整数因子.
While answering another, I stumbled over the question how I actually could find all factors of an integer number without the Symbolic Math Toolbox.
例如:
factor(60)
返回:
2 2 3 5
unique(factor(60))
因此将返回所有缺少的素数,"1" .
would therefore return all prime-factors, "1" missing.
2 3 5
我正在寻找一个可以返回所有因子的函数( 1 和数字本身并不重要,但它们会很好)
And I'm looking for a function which would return all factors (1 and the number itself are not important, but they would be nice)
x = 60
的预期输出:
Intended output for x = 60
:
1 2 3 4 5 6 10 12 15 20 30 60
我想出了一个相当庞大的解决方案,除了可以将其向量化之外,还没有任何优雅的解决方案吗?
I came up with that rather bulky solution, apart from that it probably could be vectorized, isn't there any elegant solution?
x = 60;
P = perms(factor(x));
[n,m] = size(P);
Q = zeros(n,m);
for ii = 1:n
for jj = 1:m
Q(ii,jj) = prod(P(ii,1:jj));
end
end
factors = unique(Q(:))'
我还认为,对于某些较大的数字,此解决方案将失败,因为烫发需要向量长度< 11.
Also I think, this solution will fail for certain big numbers, because perms requires a vector length < 11.
推荐答案
这里是六个不同实现的比较,用于查找整数因子:
Here is a comparison of six different implementations for finding factors of an integer:
function [t,v] = testFactors()
% integer to factor
%{45, 60, 2059, 3135, 223092870, 3491888400};
n = 2*2*2*2*3*3*3*5*5*7*11*13*17*19;
% functions to compare
fcns = {
@() factors1(n);
@() factors2(n);
@() factors3(n);
@() factors4(n);
%@() factors5(n);
@() factors6(n);
};
% timeit
t = cellfun(@timeit, fcns);
% check results
v = cellfun(@feval, fcns, 'UniformOutput',false);
assert(isequal(v{:}));
end
function f = factors1(n)
% vectorized implementation of factors2()
f = find(rem(n, 1:floor(sqrt(n))) == 0);
f = unique([1, n, f, fix(n./f)]);
end
function f = factors2(n)
% factors come in pairs, the smaller of which is no bigger than sqrt(n)
f = [1, n];
for k=2:floor(sqrt(n))
if rem(n,k) == 0
f(end+1) = k;
f(end+1) = fix(n/k);
end
end
f = unique(f);
end
function f = factors3(n)
% Get prime factors, and compute products of all possible subsets of size>1
pf = factor(n);
f = arrayfun(@(k) prod(nchoosek(pf,k),2), 2:numel(pf), ...
'UniformOutput',false);
f = unique([1; pf(:); vertcat(f{:})])'; %'
end
function f = factors4(n)
% http://rosettacode.org/wiki/Factors_of_an_integer#MATLAB_.2F_Octave
pf = factor(n); % prime decomposition
K = dec2bin(0:2^length(pf)-1)-'0'; % all possible permutations
f = ones(1,2^length(pf));
for k=1:size(K)
f(k) = prod(pf(~K(k,:))); % compute products
end;
f = unique(f); % eliminate duplicates
end
function f = factors5(n)
% @LuisMendo: brute-force implementation
f = find(rem(n, 1:n) == 0);
end
function f = factors6(n)
% Symbolic Math Toolbox
f = double(evalin(symengine, sprintf('numlib::divisors(%d)',n)));
end
结果:
>> [t,v] = testFactors();
>> t
t =
0.0019 % factors1()
0.0055 % factors2()
0.0102 % factors3()
0.0756 % factors4()
0.1314 % factors6()
>> numel(v{1})
ans =
1920
尽管第一个矢量化版本是最快的,但是由于自动JIT优化,等效的基于循环的实现(factors2
)也相差不远.
Although the first vectorized version is the fastest, the equivalent loop-based implementation (factors2
) is not far behind, thanks to automatic JIT optimization.
请注意,我必须禁用蛮力实现(factors5()
),因为它会引发内存不足错误(以双精度存储向量1:3491888400
时需要超过26GB的内存!).对于大整数,无论是在空间上还是时间上,这种方法显然都不可行.
Note that I had to disable the brute-force implementation (factors5()
) because it throws an out-of-memory error (storing the vector 1:3491888400
in double-precision requires over 26GB of memory!). This method is obviously not feasible for large integers, neither space- or time-wise.
结论:使用以下矢量化实现:)
Conclusion: use the following vectorized implementation :)
n = 3491888400;
f = find(rem(n, 1:floor(sqrt(n))) == 0);
f = unique([1, n, f, fix(n./f)]);
这篇关于整数的因式分解的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!