Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
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"; }'

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1103220]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (4)
As of 2024-04-25 18:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found