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

[Mel]

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 ?"
[ ... ]
> Here is what I have so far. Initially the get_factors function just
> iterated over the entire range(2, n + 1), but since a number can't
> have a factor greater than half of itself, I tried to shorten the
> range by doing range(2, n //2), but that still leaves 300 billion
> numbers to go through.
> 
> def get_factors(number):
>     factors = [number]
> 
>     for n in range(2, number // 2):
>         if number % n == 0:
>             factors.append(n)
> 
>     return factors
> 
> 
> def get_primes(number_list):
>     primes = number_list[:]
> 
>     for n in number_list:
>         for x in range(2, n):
>             if n % x == 0:
>                 primes.remove(n)
>                 break
> 
>     return primes
> 
> 
> print(max(get_primes(get_factors(600851475143))))
> 
> 
> Also, I want to make it clear that I DO NOT WANT THE ANSWER. I really
> want to solve this myself, but the reason I'm asking about it is to
> see if there really is some way to change this code so that it can get
> an answer in less than one minute, as the website says should be
> possible. A hint about what I need to do would be nice, but not an
> answer. I just don't see any way to get the factors without iterating
> over the entire range of values, though.

It certainly can be done faster.  I ran it against the factor finder that I 
wrote, and it popped up the answer

mwilson at tecumseth:~$ bin/factors.py 600851475143
71 839 1471 ...

before I could glance at my watch.  factors.py works, as does yours, by 
testing for small factors first, but it divides them out as it goes, so it 
tends to do its work on smallish numbers.  And since the smallest factors 
are taken out as soon as possible, they have to be the prime ones.

	Good hunting,		Mel.