find all multiplicands and multipliers for a number
Brian Gladman
blindanagram at nowhere.net
Sun Apr 12 15:15:51 EDT 2015
On 12/04/2015 18:20, Paul Rubin wrote:
> Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
>> Um, "simple sieve"? You're using Miller-Rabin to check for candidate
>> prime factors. I don't think that counts as a simple sieve :-)
>
> How does Miller-Rabin help? It has to cost more than trial division.
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.
More information about the Python-list
mailing list