2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – mellamokb Sep 27 '12 at 18:24
1
\$\begingroup\$

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

timing

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}

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.