Find divisors for a given number

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.

[omar mk]

ok

Answer 1

[Andrei Bobrov]

N=8
K=1:8
D = K(rem(N,K)==0)

[Julian Hapke]

you can increase the speed for large N when you use

N = 82148
K = 1:ceil(N/2)
D = [K(rem(N,K)==0) N]

it's also worth mentioning, that the memory usage for K is N*8 bytes or N/2*8 bytes in the accelerated solution (so if N = 134217728, K in the original answer needs 1GB). It's nice and tidy though. Implemented into a function there should be a switch depending on N, so a loop is used when N get's too big.

[Peter]

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]

Last line should be:

D = unique([D sort(N./D)]);

Or:

D = [D sort(N./D(D~=sqrt(N)))];

Avoiding double solutions when .

Answer 2

[John D'Errico]

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.

Answer 3

[Daniel Shub]

How important is it to do quickly? What is your N?

N = 8;
x = 1:N;
x(~(rem(N, x)))

Answer 4

[David]

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.

[wwmathchat]

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]

D=find(mod(N, 1:N)==0);

for N=1000000 runs in <0.02s

Answer 5

[Kevin McCoy]

 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

[Simon Matte]

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 !!!

Answer 6

[yash]

N=8645

K=1:8645

D = K(rem(N,K)==0)