Terry Reedy <tjre...@udel.edu> writes:
>> efficient implementation will allow a solution to be obtained on a
>> modestly powered computer in less than one minute."
> If something really takes a minute in C,
> allow yourself at least 10 minutes or even more with plain CPython.
No. The idea of the Euler problems is to think up sane algorithms to
solve them, not micro-optimize or use low level languages on crappy
algorithms.
n=600851475143
for d in xrange(2,n):
if d*d > n: break
while n%d == 0: n //= d
print n
finishes on my laptop with no noticable pause. The trick is to stop
testing once you hit the square root of the number. There is at least
one extremely obvious optimization I didn't bother with (above 2, only
test odd divisors), that would have doubled the speed on top of that.
--
http://mail.python.org/mailman/listinfo/python-list
