Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re^2: Finding divisors from factors (avoid dups)

by danaj (Friar)
on Oct 09, 2014 at 06:46 UTC ( [id://1103258] : note . print w/replies, xml ) Need Help??


in reply to Re: Finding divisors from factors (avoid dups)
in thread Finding divisors from factors

> Though it appears to run in an instant on the size of problems I've thrown at it.

For more complication, we can use a pathological case:

#!/usr/bin/env perl use warnings; use strict; use bigint; my @f = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59); my @d = divisors(1922760350154212639070,@f); print "$_\n" for @d;

Generating the 131,072 divisors is taking my machine anywhere from 5 seconds to 50 seconds for the various solutions. The performance ordering is a little different for bigints than for native ints. Roboticus's simple loop is the fastest, with my non-sqrt hash solution just behind. The least memory is my sqrt hash solution but not by a lot.