find all multiplicands and multipliers for a number
no.email at nospam.invalid
Sat Apr 11 18:59:11 CEST 2015
Marko Rauhamaa <marko at pacujo.net> 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