find all multiplicands and multipliers for a number
no.email at nospam.invalid
Sun Apr 12 21:45:12 CEST 2015
Brian Gladman <blindanagram at nowhere.net> 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