find all multiplicands and multipliers for a number
Brian Gladman
blindanagram at nowhere.net
Sun Apr 12 21:07:39 CEST 2015
On 12/04/2015 15:29, Steven D'Aprano wrote:
>> I don'tknow how well it compares more generally but where large amounts
>> of memory are available a simple sieve works quite well. I have an
>> implementation available here (in Python 3):
>>
>> http://ccgi.gladman.plus.com/wp/?page_id=1500
>
> Um, "simple sieve"? You're using Miller-Rabin to check for candidate prime
> factors. I don't think that counts as a simple sieve :-)
>
What I meant here is that the underlying sieve on which factoring
depends - Primes() - is a simple one. I'm sorry that I didn't make this
clearer. I agree, of course, that the factoring code itself is more
complex than others are experimenting with but I am using it in
situations where I want it to work reasonbly well for quite large
numbers.
> so there is a quite good speedup available from using Miller-Rabin. But it's
> not a simple sieve any more.
>
> By the way, it is possible to get guaranteed deterministic
> (non-probabilistic) results with Miller-Rabin, for small integers. By small
> I mean less than 2**64. See my pyprimes for details.
Yes, I have a more complex version but the simple one works well enough
in this context and finds very large primes that would otherwise stall
the code.
Thanks for taking a look.
Brian
More information about the Python-list
mailing list