This is a big factor that works reasonably well.  The algorithm
is pretty stupid, but it works.  It will fail to work if there is a prime
factor at about 1.6e19.  But I am not concerned that people will
encounter this in practice because it will fail slooowly. :-)

The only significant improvement that I see is to have a smarter
switch to integer behaviour.  Specifically what I am thinking is
that once you switch to integer operations, you speed up a lot.
If $d, $q and $r are divisor, quotient and remainder, then the
result of $d+= 2 can be calculated by:

$d += 2;
$r -= (2*$q) % $d;
$q -= int((2*$q) / $d);
if ($r < 0) {
    $r = $d + $r;
    $q--;
}

Using this logic with Math::BigInt in effect is a huge loss.  But I
think that using this logic to move to using integer operations
sooner might be a good win..

Regards,
Ben (having fun) Tilly