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

[MRAB]

On 21/06/2011 20:48, John Salerno wrote:
> I'm working on the Project Euler exercises and I'm stumped on problem
> 3:
>
> "What is the largest prime factor of the number 600851475143 ?"
>
> Now, I've actually written functions to get a list of the factors of
> any given number, and then another function to get the prime numbers
> from that list. It works fine with small numbers, but when I try to
> feed my get_factors function with the above number (600 billion),
> naturally it takes forever! But according to the Project Euler
> website:
>
> "I've written my program but should it take days to get to the answer?
>
> Absolutely not! Each problem has been designed according to a "one-
> minute rule", which means that although it may take several hours to
> design a successful algorithm with more difficult problems, an
> efficient implementation will allow a solution to be obtained on a
> modestly powered computer in less than one minute."
>
> But it definitely takes more than a minute, and I still haven't gotten
> it to end yet without just canceling it myself.
>
[snip]
A non-prime is the product of a prime and another number which may or
may not be a prime. Look for the smallest prime and repeat.

On a modern PC, if it takes more than, say, a second for the given
number, you're doing it wrong. :-)