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]

produces 
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]
run as time perl test.pl | md5sum. The factoring and printing take some time, but less than 15% of the total for the functions above.

In reply to Finding divisors from factors by danaj

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.