How can I speed up a script that iterates over a large range (600 billion)?

[Paul Rubin]

Terry Reedy <tjreedy at udel.edu> writes:
> If the best C program for a problem takes 10 seconds or more, then
> applying the same 1 minute limit to Python is insane, and contrary to
> the promotion of good algorithm thinking.

The Euler problems are all designed to be doable in 1 minute or less and
the Euler project started in 2001, when personal computers were probably
10x slower than they are today.  So they shouldn't take more than 6
seconds on a modern computer if you're thoughtful.  On a reasonable
modern computer (maybe even a 2001 computer), they should all be doable
in < 1 minute in python, probably well under.  They can probably all be
done in under 1 second in C.

The "largest prime factor of 600851475143" problem we're discussing took
0.017 user cpu seconds in completely unoptimized python on my laptop
using the second-most-naive algoritm possible, including loading the
interpreter from the command line.  Executing an empty file takes the
same amount of time.  The algorithm would probably be >10x faster in C
with a little bit of tweaking.  The problems are about math cleverness,
not CPU resources.  Some of them are pretty hard, but if your solution
is taking more than a minute in Python, it means you should be looking
for a better algorithm, not a faster language.