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

Question

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.

Answer 1

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}

Answer 2

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