Marko Rauhamaa <ma...@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. -- https://mail.python.org/mailman/listinfo/python-list
