http://qs321.pair.com?node_id=1103220


in reply to Finding divisors from factors

Munging my C code, here is one that is faster, though not simpler:

sub divisors { my($n,@f) = @_; my @d = (1); while (@f) { my $p = shift(@f); if (!@f || $p != $f[0]) { # Factor appears once. Multiply through. push @d, map { $p * $_ } @d; } else { my $e = 1; do { shift(@f); $e++; } while @f && $p == $f[0]; # Factor appears $e times. Multiply through p, p^2, p^3, ... my @t = @d; for (1 .. $e) { @t = map { $p * $_ } @t; push @d, @t; } } } @d = sort { $a <=> $b } @d; @d; }

I'm basically converting to factor/exponent form, then pushing the divisors on the list. Doing it by prime factor means we avoid duplication so no need for hashes. Improvements welcome.

An aside, we can see some expected results using something like:
perl -MMath::Pari=divisors -E 'for my $n (1..1_000_000) { my $d = divisors($n); print "$n @$d\n"; }'
or
perl -Mntheory=divisors -E 'for my $n (1..1_000_000) { my @d = divisors($n); print "$n @d\n"; }'