Re^2: Finding divisors from factors

Thanks Rolf.

The powerset solution was mainly to point out this simple way. It does work -- one just needs to remove duplicates using a hash.

It looks like your solution is very similar to my followup, we just do the multiply through a little different. The time is pretty close, and both faster than my earlier solutions.

They also have the advantage of not doing excess computation, which is important when we move to bigints where every operation is expensive (with Math::BigInt at least).

Comment on Re^2: Finding divisors from factors

Replies are listed 'Best First'.

Re^3: Finding divisors from factors (updated)
by LanX (Saint) on Oct 09, 2014 at 09:19 UTC

This needs only one multiplication per divisor, hence its O(#D) i.e. <= O(2^#P) for worst case, that's pretty optimal.

But I like the simplicity and readability compared to other suggestions, so personally I wouldn't start micro optimization now just to save 10 or 20 %.

update

Cheers Rolf

_{(addicted to the Perl Programming Language and ☆☆☆☆ :)}

°) or moving data or linearizing loops

update

E.G. you could try to replace the maps with direct

push @D_new, ($_*$p) for @D

expressions!

This ~~could~~ should be faster... but I'm not very motivated to benchmark myself. :)

[reply]
[d/l]


Do you know where your variables are?
	PerlMonks