On 21-06-11 21:48, 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 ?"
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!
You need a better algorithm to calculate primes, and iterate over primes
instead of over the full (half, or even better, sqrt(n)) range of
possible values. You also should optimize the stop condition, once you
find that the number can no longer be divided by larger primes you can
stop the loop.
For instance to get the prime factors of the number 1000 you'd iterate
over the prime numbers 2,3,5 and conclude that
1000=2*2*2*5*5*5, so 5 would be the largest prime factor.
No need to try larger primes than 5, let alone go through 1..sqrt(1000).
The Sieve of Eratosthenes is a well known algorithm to calculate primes
with reasonable efficiency.
Irmen
--
http://mail.python.org/mailman/listinfo/python-list
