Find divisors for a given number

135 次查看（过去 30 天）
Lulu
Lulu 2011-11-17
回答： yash 2023-9-15
Hello,
I need to find all possible divisors D for a given number N that provide integers in N/D. For instance, if N=8, then D should be 1,2,4,8. How can I quickly do thin in MATLAB?
Thanks.

请先登录，再回答此问题。

采纳的回答

Andrei Bobrov
Andrei Bobrov 2011-11-17
N=8
K=1:8
D = K(rem(N,K)==0)
  3 个评论
显示 1更早的评论
Peter
Peter 2020-3-6
Further increase in speed, as you only need to go to sqrt(N) due to symmetry:
N = 999999;
K = 1:ceil(sqrt(N));
D = K(rem(N,K)==0);
D = [D sort(N./D)];
chicken vector
chicken vector 2023-1-25
Last line should be:
D = unique([D sort(N./D)]);
Or:
D = [D sort(N./D(D~=sqrt(N)))];
Avoiding double solutions when .

请先登录，再进行评论。

更多回答（5 个）

John D'Errico
John D'Errico 2020-3-8
编辑：John D'Errico 2020-3-8
If you are allowed to use factor to determine the prime factors, then it is pretty easy. You also never need to get stuck in the trap of memory limits.
function divs = alldivisors(N)
% compute the set of all integer divisors of the positive integer N
% first, get the list of prime factors of N.
facs = factor(N);
divs = [1,facs(1)];
for fi = facs(2:end)
% if N is prime, then facs had only one element,
% and this loop will not execute at all, In that case
% The set of all divisors is simply 1 and N.
% this outer product will generate all combinations of
% the divisors found so far, combined with the current
% divisor fi.
divs = [1;fi]*divs;
% unique eliminates the replicate divisors, making
% this an efficient code.
divs = unique(divs(:)');
end
end
Does it work? yes. And it will never, EVER cause memory problems.
alldivisors(17)
ans =
1 17
alldivisors(144)
ans =
1 2 3 4 6 8 9 12 16 18 24 36 48 72 144
alldivisors(30)
ans =
1 2 3 5 6 10 15 30
And now for something that will get lengthy, consider this one:
alldivisors(factorial(10))
ans =
Columns 1 through 7
1 2 3 4 5 6 7
Columns 8 through 14
8 9 10 12 14 15 16
Columns 15 through 21
18 20 21 24 25 27 28
Columns 22 through 28
30 32 35 36 40 42 45
Columns 29 through 35
48 50 54 56 60 63 64
Columns 36 through 42
70 72 75 80 81 84 90
Columns 43 through 49
96 100 105 108 112 120 126
Columns 50 through 56
128 135 140 144 150 160 162
Columns 57 through 63
168 175 180 189 192 200 210
Columns 64 through 70
216 224 225 240 252 256 270
Columns 71 through 77
280 288 300 315 320 324 336
Columns 78 through 84
350 360 378 384 400 405 420
Columns 85 through 91
432 448 450 480 504 525 540
Columns 92 through 98
560 567 576 600 630 640 648
Columns 99 through 105
672 675 700 720 756 768 800
Columns 106 through 112
810 840 864 896 900 945 960
Columns 113 through 119
1008 1050 1080 1120 1134 1152 1200
Columns 120 through 126
1260 1280 1296 1344 1350 1400 1440
Columns 127 through 133
1512 1575 1600 1620 1680 1728 1792
Columns 134 through 140
1800 1890 1920 2016 2025 2100 2160
Columns 141 through 147
2240 2268 2304 2400 2520 2592 2688
Columns 148 through 154
2700 2800 2835 2880 3024 3150 3200
Columns 155 through 161
3240 3360 3456 3600 3780 3840 4032
Columns 162 through 168
4050 4200 4320 4480 4536 4725 4800
Columns 169 through 175
5040 5184 5376 5400 5600 5670 5760
Columns 176 through 182
6048 6300 6400 6480 6720 6912 7200
Columns 183 through 189
7560 8064 8100 8400 8640 8960 9072
Columns 190 through 196
9450 9600 10080 10368 10800 11200 11340
Columns 197 through 203
11520 12096 12600 12960 13440 14175 14400
Columns 204 through 210
15120 16128 16200 16800 17280 18144 18900
Columns 211 through 217
19200 20160 20736 21600 22400 22680 24192
Columns 218 through 224
25200 25920 26880 28350 28800 30240 32400
Columns 225 through 231
33600 34560 36288 37800 40320 43200 44800
Columns 232 through 238
45360 48384 50400 51840 56700 57600 60480
Columns 239 through 245
64800 67200 72576 75600 80640 86400 90720
Columns 246 through 252
100800 103680 113400 120960 129600 134400 145152
Columns 253 through 259
151200 172800 181440 201600 226800 241920 259200
Columns 260 through 266
302400 362880 403200 453600 518400 604800 725760
Columns 267 through 270
907200 1209600 1814400 3628800
For something even bigger, how about factorial(15)?
N = factorial(15)
N =
1307674368000
numel(alldivisors(N))
ans =
4032
timeit(@() alldivisors(N))
ans =
0.004247201051
All 4032 divisors of that really big number, in all of 0.004 seconds of CPU time.
Daniel Shub
Daniel Shub 2011-11-17
How important is it to do quickly? What is your N?
N = 8;
x = 1:N;
x(~(rem(N, x)))
David
David 2013-7-24
D=[1; unique(cumprod(perms(factor(N)),2))]
This allows large N (limit is N<2^32) provided that N do not have too many (>10) primary dividers, e.g. N=1000001 will work but N=1000000 will run out of memory and fail.
  2 个评论
wwmathchat
wwmathchat 2020-3-7
编辑：wwmathchat 2020-3-8
Nice. I've updated your solution to avoid the memory problem.
prime_factors = factor(N);
Nl = length(prime_factors);
% The divisors are the products of each subset of the prime factors.
% Use nchoosek(prime_factors,k) for k = 1,2, ..., Nl to get the subsets
% take product of each
divisors = [];
for k = 1:Nl
sets_length_k = nchoosek(prime_factors,k);
divisors = [divisors;
unique(prod(sets_length_k,2))];
end
divisors = [1;unique(divisors)];
Stefan Spulber
Stefan Spulber 2021-2-12
D=find(mod(N, 1:N)==0);
for N=1000000 runs in <0.02s

请先登录，再进行评论。

Kevin McCoy
Kevin McCoy 2016-7-21
function d = divisors( n )
%DIVISORS(N) Returns array of divisors of n
if ~isscalar(n)
error('n must be a scalar');
end
if n < 1
error('n must be positive integer');
end
if n == 1
d = 1;
return;
end
f = factor(n);
pf = unique(f);
for i = 1:length(pf)
m(i) = sum(f == pf(i));
end
mi = zeros(size(m));
d = zeros(1,prod(m+1));
i = 1;
carry = 0;
while ~carry
d(i) = prod(pf.^mi);
i = i + 1;
if mi(1) < m(1)
mi(1) = mi(1) + 1;
else
mi(1) = 0;
carry = 1;
end
for j = 2:length(m)
if carry
if mi(j) < m(j)
mi(j) = mi(j) + 1;
carry = 0;
else
mi(j) = 0;
carry = 1;
end
end
end
end
d = sort(d);
end
  1 个评论
Simon Matte
Simon Matte 2018-3-16
I stumbled upon this while looking for a fast (custom) way to calculate every divisors of a number given its prime factors. I was trying to build (a variable amount of) nested loops to multiply factors together, it was a nightmare.
I'll be borrowing that, it's amazing. Thank you !!!

请先登录，再进行评论。

yash
yash 2023-9-15
N=8645
K=1:8645
D = K(rem(N,K)==0)

类别

在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by