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