find all multiplicands and multipliers for a number

Paul Rubin at nospam.invalid
Sat Apr 11 18:59:11 CEST 2015

Marko Rauhamaa <marko at> writes:
> This is slightly faster:...
> def fac(n):
>     for c in range(n):
>         if c*c > n: ...

That's interesting and says something bad about generators in Python 3.
It's doing 3 times as many trial divisions as the version I posted, and
it's still faster?

xrange in Python 2 doesn't work with bignums, but using 
itertools.count(3,2) I get about 5.5 seconds and with itertools.count(3)
I get 11 seconds.

I wrote the same algorithm in Haskell and it's about 0.85 seconds,
probably due to native compilation and faster bignums.  A naive
implementation of Pollard's rho algorithm in Haskell is basically
instantaneous on that number.  I might try coding Pollard's method or
Brent's improvement in Python.

More information about the Python-list mailing list