find all multiplicands and multipliers for a number

Brian Gladman blindanagram at nowhere.net
Sun Apr 12 21:15:51 CEST 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