We don't bite newbies here... much PerlMonks

### Re: Finding divisors from factors

by danaj (Friar)
 on Oct 08, 2014 at 20:35 UTC 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;
}
[download]```

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 having an uproarious good time at the Monastery: (5)
As of 2024-02-24 03:04 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (22 votes). Check out past polls.