Assuming I have a (sorted) list of prime factors of a number, I would like to create a sorted list of divisors. How can we do this as fast as possible with Perl code?

For example:

use ntheory qw/:all/;
my $n = 183092192580;
print "Factors:  @{[factor($n)]}\n";
print "Divisors: @{[divisors($n)]}\n";
[download]

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 1664474478 2774124130 3051536543 3328948956 4161186195 5548248260 6103073086 8322372390 9154609629 12206146172 15257682715 16644744780 18309219258 30515365430 36618438516 45773048145 61030730860 91546096290 183092192580

We can view this as the unique list of products of the powersets. For instance using the simple powerset from RosettaCode yields this rather slow method:

sub divisors {
  my($n,@factors) = @_;
  my %divisors;
  foreach my $l ( powerset(@factors) ) {
    my $d = 1;
    $d *= $_ for @$l;
    undef $divisors{$d};
  }
  my @d = sort { $a<=>$b } keys %divisors;
  @d;
}
sub powerset {@_ ? map { $_,[$_[0], @$_] } powerset(@_[1..$#_]) : [];}
[download]

Here is one possibility that runs about 4x faster:

sub divisors {
  my($n,@factors) = @_;

  my %all_factors;
  foreach my $f (@factors) {
    my @to_add = grep { $_ < $n }
                 map { $f * $_ }
                 keys %all_factors;
    undef @all_factors{ $f, @to_add };
  }
  # 3. Add 1 and n, sort.
  undef $all_factors{1};
  undef $all_factors{$n};
  my @divisors = sort {$a<=>$b} keys %all_factors;
  @divisors;
}
[download]

Note that the divisors are symmetric about sqrt(n) so if we had the bottom portion 1 .. sqrt(n) in the sorted array @d then we could quickly fill the rest using push @d, map { $_*$_ == $n ? () : int($n/$_) } reverse @d; This can be crudely applied to the solution above to yield this slightly faster solution:

sub divisors {
  my($n,@factors) = @_;
  my $sqrtn = int(sqrt($n));

  my %all_factors;
  foreach my $f ( grep { $_ <= $sqrtn } @factors) {
    my @to_add = grep { $_ <= $sqrtn }
                 map { $f * $_ }
                 keys %all_factors;
    undef @all_factors{ $f, @to_add };
  }
  undef $all_factors{1};
  my @d = sort {$a<=>$b} keys %all_factors;
  @d, map { $_*$_ == $n ? () : int($n/$_) } reverse @d;
}
[download]

Anything faster and/or simpler? We can use something crude like this to test:

#!/usr/bin/env perl
use warnings;
use strict;
use ntheory qw/factor/;
srand(1);

for (1..100000) {
  my $n = int(rand(2**36));
  my @d = divisors($n,factor($n));
  print "$n @d\n";
}
[download]