Re: Finding divisors from factors

First of all powerset is wrong cause equal factors will produce duplicates, e.g.

P{2,2} = { (,),(2,),(,2),(2,2)}

Then I doubt you can multiply in a way which produces all divisors in a sorted way, so final sorting can't be avoided.

I'd try a recursive/iterative approach,

initialize the result set D with 1
shift the smallest prime p' from P
multiply all divisors in the temporary result set D with p' to get D'
push the new divisors D' into D
continue with step 2 till P empty
sort D

but note you'll need a test if p' and p'' are duplicates to avoid the aforementioned problem! :)

update

looks good! :)

use warnings;
use strict;

my @P = qw/2 2 3 5 11 277412413/;
@P= sort { $a<=>$b } @P;              # sort to be sure

my @D     = (1);
my @D_new = ();
my $p_old = 0;

for my $p (@P) {
    if ( $p == $p_old ) {
        @D_new = map { $_* $p } @D_new;
    } else {
        @D_new = map { $_* $p } @D;
    }
    push @D,@D_new;
    $p_old = $p;
}

@D= sort { $a<=>$b } @D;

print "Factors @P\n";
print "Divisors: @D\n";
[download]

out

Factors 2 2 3 5 11 277412413
Divisors: 1 2 3 4 5 6 10 11 12 15 20 22 30 33 44 55 60 66 110 132 165 
+220 330 660 277412413 554824826 832237239 1109649652 1387062065 16644
+74478 2774124130 3051536543 3328948956 4161186195 5548248260 61030730
+86 8322372390 9154609629 12206146172 15257682715 16644744780 18309219
+258 30515365430 36618438516 45773048145 61030730860 91546096290 18309
+2192580
[download]

Cheers Rolf

_{(addicted to the Perl Programming Language and ☆☆☆☆ :)}

Comment on Re: Finding divisors from factors Select or Download Code

Replies are listed 'Best First'.
Re^2: Finding divisors from factors by danaj (Friar) on Oct 08, 2014 at 22:27 UTC
Thanks Rolf. The powerset solution was mainly to point out this simple way. It does work -- one just needs to remove duplicates using a hash. It looks like your solution is very similar to my followup, we just do the multiply through a little different. The time is pretty close, and both faster than my earlier solutions. They also have the advantage of not doing excess computation, which is important when we move to bigints where every operation is expensive (with Math::BigInt at least).	[reply]
Re^3: Finding divisors from factors (updated) by LanX (Saint) on Oct 09, 2014 at 09:19 UTC
Of course you can still speed up this solution, but I doubt it would be more than micro optimizations or just related to Perl specific features/bottlenecks (like overhead for allocating temporary arrays) ° This needs only one multiplication per divisor, hence its O(#D) i.e. <= O(2^#P) for worst case, that's pretty optimal. But I like the simplicity and readability compared to other suggestions, so personally I wouldn't start micro optimization now just to save 10 or 20 %. update Of course I'm not comparing to solutions using XS modules. In that case just use C directly. Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :)} °) or moving data or linearizing loops update E.G. you could try to replace the maps with direct `push @D_new, ($_*$p) for @D` expressions! This ~~could~~ should be faster... but I'm not very motivated to benchmark myself. :)	[reply] [d/l]