find all multiplicands and multipliers for a number

[wolfram.hinderer at googlemail.com]

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.