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

[Tim Roberts]

Mel <mwilson at the-wire.com> wrote:
>
>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.

That's a great hint, and I'm not sure it would have occurred to me on my
own.  Using your hint, I was able to write a 16-line script that also
produced a result instantaneously.  Very satisfying.

I'm going to save that one...
-- 
Tim Roberts, timr at probo.com
Providenza & Boekelheide, Inc.