http://www.perlmonks.org?node_id=482073


in reply to Re^2: Algorithm for cancelling common factors between two lists of multiplicands
in thread Algorithm for cancelling common factors between two lists of multiplicands

For simple problems I usually use something like this:

{ my @p; BEGIN { @p = (2, 3) } sub nextprime { my $p = $p[$#p]; DIV: while (1) { $p += 2; my $pc = 0; while (1) { my $d = $p[$pc++]; last if $d * $d > $p; next DIV unless $p % $d; } $p[@p] = $p; return $p; } } sub factors { my $n = shift; my($pc, @result) = (0); while ($n > 1) { my $d = $p[$pc++] || nextprime(); if ($d * $d > $n) { push @result, $n; $n = 1; } else { while ($n % $d == 0) { $n /= $d; push @result, $d; } } } \@result; } }

The rest of the time I use Math::Big*, sometimes with Pari or (lately) GMP.

Hugo