Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: Finding divisors from factors

by danaj (Friar)
on Oct 08, 2014 at 20:35 UTC ( [id://1103220] : note . print w/replies, xml ) Need Help??


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"; }'