# find all multiplicands and multipliers for a number

Sun Apr 12 01:17:29 CEST 2015

```Am Samstag, 11. April 2015 09:14:50 UTC+2 schrieb Marko Rauhamaa:
> Paul Rubin <no.email at nospam.invalid>:
>
> > This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
> > laptop (64 bit linux):
>
> Converted to Python3:
> ========================================================================
> #!/usr/bin/env python3
>
> import itertools, time
>
> def candidates():
>     yield 2
>     yield 3
>     for i in itertools.count(5,6):
>         yield i
>         yield i+2
>
> def fac(n):
>     for c in candidates():
>         if c*c > n:
>             yield n
>             break
>         while n%c == 0:
>             yield c
>             n //= c
>
> t0 = time.time()
> print(list(fac(2**111+1)))
> print(time.time() - t0)
> ========================================================================
>
> This is slightly faster:
>
> ========================================================================
> #!/usr/bin/env python3
>
> import time
>
> def fac(n):
>     for c in range(n):
>         if c*c > n:
>             yield n
>             break
>         while n%c == 0:
>             yield c
>             n //= c
>
> t0 = time.time()
> print(list(fac(2**111+1)))
> print(time.time() - t0)
> ========================================================================
>

I get other results on 3.2.3:

n % 0 raises ZeroDivisionError.
After fixing that by using range(2, n) it takes about three times as long as the original version, which is what I'd expect.

```