Of course you can still speed up this solution, but I doubt it would be more than micro optimizations or just related to Perl specific features/bottlenecks (like overhead for allocating temporary arrays) °

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

Of course I'm not comparing to solutions using XS modules. In that case just use C directly.

°) 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. :)