find all multiplicands and multipliers for a number

[Brian Gladman]

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.