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