find all multiplicands and multipliers for a number

Paul Rubin at nospam.invalid
Sun Apr 12 21:45:12 CEST 2015

Brian Gladman <blindanagram at> writes:
> As we factor the number with increasing prime values from a simple
> sieve, if the number remaining to be factored is still large it can then
> be efficient to run a prime test to see if what remains is prime.

In the case of 2**111+1, the second-largest prime factor is larger than
the sqrt of the largest one.  Therefore, the obvious trial division
strategy should have stopped as soon as the second-largest factor was
found, since what remained had to be prime.  I agree that this logic
doesn't apply to something like the rho algorithm, where you get a
factor that might not be the smallest one.

More information about the Python-list mailing list