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! -- http://mail.python.org/mailman/listinfo/python-list