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

[MRAB]

On 22/06/2011 06:58, Chris Torek wrote:
> Now that the exercise has been solved...
>
> Instead of "really short code to solve the problem", how about
> some "really long code"? :-)
>
> I was curious about implementing prime factorization as a generator,
> using a prime-number generator to come up with the factors, and
> doing memoization of the generated primes to produce a program that
> does what "factor" does, e.g.:
>
>      $ factor 99999999999999999
>      99999999999999999: 3 3 2071723 5363222357
>
> The python code is rather too slow for this particular number (I
> gave up on it finding 5363222357) but works quite well on 600851475143,
> or even, e.g., 12186606004219:
>
>      $ python factor.py 600851475143 12186606004219
>      600851475143: 71 839 1471 6857
>      12186606004219: 2071723 5882353
>
[snip]
This code isn't particularly efficient, but it's fast enough:

import math

n = 99999999999999999
limit = math.sqrt(n)
test = 2
factors = []
while test <= limit:
     if n % test == 0:
         factors.append(test)
         n //= test
         limit = math.sqrt(n)
     else:
         test += 1

factors.append(n)

print(factors)