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

[Irmen de Jong]

On 21-06-11 21: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!

You need a better algorithm to calculate primes, and iterate over primes 
instead of over the full (half, or even better, sqrt(n)) range of 
possible values. You also should optimize the stop condition, once you 
find that the number can no longer be divided by larger primes you can 
stop the loop.

For instance to get the prime factors of the number 1000 you'd iterate
over the prime numbers 2,3,5 and conclude that

1000=2*2*2*5*5*5, so 5 would be the largest prime factor.

No need to try larger primes than 5, let alone go through 1..sqrt(1000).

The Sieve of Eratosthenes is a well known algorithm to calculate primes 
with reasonable efficiency.

Irmen