# given prime factors of a number, what is the fastest way to calculate it's proper divisors? [closed]

Given prime factors of a number, what is the fastest way to calculate divisors?

``````clc; clear;
sms=0;
count = 1;
x=0;
for i=11:28123
fac = factor(i);
sm = 1;
for j = 1:length(fac)-1
sm = sm + sum(prod(unique(combntns(fac,j), 'rows'),2));
end
if sm>i
x(count) = i;
count = count + 1;
end
end
sum1=0;
count = 1;
for i=1:length(x)
for j=i:length(x)
smss = x(i) + x(j);
if smss <= 28123
sum1(count) = smss;
count = count + 1;
end
end
end
sum1 = unique(sum1);
disp(28123*28124/2-sum(sum1));
``````

currently I'm using this `prod(unique(combntns(fac,j), 'rows'),2)` code which is awfully slow and I'm using Matlab.

-
I don't know `Matlab`, but given factors `a_0^k_0 * a_1^k_1 * ... * a_n^k_n`, the sum of the proper divisors is given as `(a_0^0 + a_0^1 + ... + a_0^k_0) * (a_1^0 + a_1^1 + ... + a_1^k_1) * ... * (a_n^0 + a_n^1 + ... + a_n^k_n)`, which should be a pretty fast formula to calculate manually. – mellamokb Sep 27 '12 at 18:24

## closed as off topic by Peter Taylor, Gareth, Matt, boothby, VenteroOct 1 '12 at 10:56

Questions on Programming Puzzles & Code Golf Stack Exchange are expected to relate to programming puzzle or code golf within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

# Mathematica

``````Union[Prepend[Times @@@ Rest@Subsets@l, 1]]
``````

Usage

I'm assuming that repeated factors would be repeated in the list of factors, as below:

``````l = {2, 2, 3, 5, 5, 11, 11, 11, 31, 37, 617};
Union[Prepend[Times @@@ Rest@Subsets@l, 1]]//AbsoluteTiming
``````

This routine is much slower than the built in function `Divisors`, which has to first factor the Integer. I am fairly certain that `Divisors` is compiled.

``````Divisors[282584210700]; // AbsoluteTiming
``````

{0.000262, Null}

-

Haskell (with `Data.List`)

``````f :: [Int] -> [Int]
f [] = [1]
f (x:xs) = a ++ map (x*) a
where a=f xs
factorsfromlist1 = nub . sort . f
-- may have better performance
factorsfromlist2 = map head . group . sort . f
``````

On the list `[2, 2, 3, 5, 5, 11, 11, 11, 17, 31, 37, 47, 67, 103, 331, 617, 1093, 1597, 2309]`:

``````\$ ghc -O test.hs
\$ ./test
Prime factors of 2078661171193247994962581628700
Method 1: 1.077712s
Method 2: 0.863675s
``````
-