An efficient way to compute all divisors, given a prime factorization , is to loop through the exponents with a mixed-radix Gray code with radices , and then multiply or divide the previously computed divisor by , depending on whether the -th exponent is increased or decreased.
|
| (1.2) |
Extract the lists of the bases and exponents.
|
>
|
b := map2(op,1,f);
e := map2(op,2,f);
|
|
| |
|
| (1.3) |
Create a MixedRadixGrayCode iterator using the append_change option so the last index contains a signed value of the index that changed (the initial value of the index is 0).
|
>
|
G := MixedRadixGrayCode(e +~ 1, append_change):
|
Get the position of the index that indicates the change. The output method of the iterator object, , returns the Array that is used to output the results.
|
>
|
n := upperbound(output(G)):
|
Update and return the divisor () given , a vector whose -th slot stores the index of the prime that changed, with a positive value indicating an increase by one and a negative value, a decrease by one.
|
>
|
update_d := proc(g,b,n)
global d;
local i;
i := g[n];
if i < 0 then d := d/b[-i];
elif i > 0 then d := d*b[+i];
else d := 1;
end if;
return d;
end proc:
|
Use the iterator and procedure to compute all divisors.
|
>
|
[seq(update_d(g,b,n), g = G)];
|
|
| (1.4) |
