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