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

John Salerno johnjsal at gmail.com
Tue Jun 21 15:48:51 EDT 2011


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.

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.

Thanks!



More information about the Python-list mailing list