On 21/06/2011 20: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! 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.
[snip]
A non-prime is the product of a prime and another number which may or
may not be a prime. Look for the smallest prime and repeat.
On a modern PC, if it takes more than, say, a second for the given
number, you're doing it wrong. :-)
--
http://mail.python.org/mailman/listinfo/python-list
