On Sun, 12 Apr 2015 07:34 pm, Brian Gladman wrote: > On 11/04/2015 03:04, Steven D'Aprano wrote: > >> It may be a bit slow for very large numbers. On my computer, this takes >> 20 seconds: >> >> py> pyprimes.factors.factorise(2**111+1) >> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L] >> >> >> but that is the nature of factorising large numbers. >> >> http://code.google.com/p/pyprimes/source/browse/ > > 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 :-) > where: > >>>> from number_theory import factors >>>> print(tuple(factor(2 ** 111 + 1))) > ((3, 2), (1777, 1) , (3331, 1), (17539, 1), (25781083, 1), > (107775231312019, 1)) > > runs in less than 2 seconds on my laptop. Although it is not directly comparable to the sieve version I used above, on my machine I get: py> import number_theory py> with Stopwatch(): ... list(number_theory.factors(2**111+1)) ... [3, 3, 1777, 3331, 17539, 25781083, 107775231312019] time taken: 5.823970 seconds 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. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
