Brian Gladman <blindanag...@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. -- https://mail.python.org/mailman/listinfo/python-list
