# 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

# 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