I make no claim that this is the fastest approach. It is likely slower because rather than an optimized call to sort, it does merge sorts as it goes (which might be faster if I were doing those merge sorts in C more like sort works). It also likely uses more memory than many solutions.
Though it appears to run in an instant on the size of problems I've thrown at it.
I only post it because I liked that I was able to avoid having to detect duplicates. I don't bother to do the multiplication to compute a divisor if it would end up being a duplicate.
#!/usr/bin/perl -w
use strict;
my %f = ( 2 => 2, 3 => 1, 5 => 1, 11 => 1, 277412413 => 1 );
my @f = sort { $a <=> $b } keys %f;
my @d = @f;
my( %d, %x );
for my $i ( 0..$#f ) {
my $f = $f[$i];
( $d{$f} = [(0)x@f] )->[$i]++;
$x{$f} = $i;
}
for my $i ( 0..$#f ) {
my $f = $f[$i];
my $p = $f{$f};
my @t = @d;
for my $e ( 1..$f{$f} ) {
my( @t2, @m, @n );
while( @t ) {
my $t = shift @t;
merge( \@n, $t, \@m, 1 < $e ? \@d : () );
push @n, $t
if 1 == $e;
if( $d{$t}[$i] < $p
&& $x{$t} <= $i # Avoid duplicates
) {
my $m = $t*$f;
push @m, $m;
push @t2, $m;
( $d{$m} = [@{ $d{$t} }] )->[$i]++;
$x{$m} = $i
if ! $x{$m} || $x{$m} < $i;
}
}
@t = @t2;
merge( \@n, 0, \@m, 1 < $e ? \@d : () );
@d = @n;
}
}
print "Factors:";
for my $f ( @f ) {
if( 1 < $f{$f} ) {
print " $f^$f{$f}";
} else {
print " $f";
}
}
print "\nDivisors: 1 @d\n";
exit;
sub merge {
my( $to_av, $max, $from_av, @rest ) = @_;
if( $max ) {
while( @$from_av && $from_av->[0] < $max ) {
my $next = shift @$from_av;
merge( $to_av, $next, @rest )
if @rest;
push @$to_av, $next;
}
merge( $to_av, $max, @rest )
if @rest;
} elsif( @rest ) {
while( @$from_av ) {
my $next = shift @$from_av;
merge( $to_av, $next, @rest );
push @$to_av, $next;
}
merge( $to_av, 0, @rest );
} else {
push @$to_av, @$from_av;
@$from_av = ();
}
}
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