use ntheory qw/:all/;
my $n = 183092192580;
print "Factors: @{[factor($n)]}\n";
print "Divisors: @{[divisors($n)]}\n";
####
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..$#_]) : [];}
##
##
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;
}
##
##
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;
}
##
##
#!/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";
}