Mel mwil...@the-wire.com wrote:
It certainly can be done faster. I ran it against the factor finder that I
wrote, and it popped up the answer
mwilson@tecumseth:~$ bin/factors.py 600851475143
71 839 1471 ...
before I could glance at my watch. factors.py works, as does yours, by
testing for
As a general note concerning the use of Python on Project Euler, and
the one minute guideline.
For problems 1-100, each problem is easily solved in less than 1
minute processing time *if* the algorithms and math is done right
and with thought.
My project Euler scripts solves the first 100
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
Chris Torek nos...@torek.net writes:
def primes():
Yields sequence of prime numbers via Sieve of Eratosthenes.
I think this has the same order-complexity but is enormously slower in
practice, and runs out of recursion stack after a while. Exercise: spot
the recursion.
from
On Tue, Jun 21, 2011 at 11:58 PM, Chris Torek nos...@torek.net wrote:
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,
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
On Wed, Jun 22, 2011 at 10:01 PM, Anny Mous b1540...@tyldd.com wrote:
prime = table[i]
del table[i]
I don't fully understand your algorithm, but I think these two lines
can be rewritten as:
prime=table.pop(i)
Interesting algo. A recursive generator, not sure I've seen
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
On Wed, Jun 22, 2011 at 6:01 AM, Anny Mous b1540...@tyldd.com wrote:
def sieve():
Yield prime integers efficiently.
This uses the Sieve of Eratosthenes, modified to generate the primes
lazily rather than the traditional version which operates on a fixed
size array of integers.
On 22-6-2011 5:02, John Salerno wrote:
Thanks. So far they are helping me with Python too, but definitely not
as much as more general exercises would, I'm sure. The part about
writing the code is fun, but once that's done, I seem to end up stuck
with an inefficient implementation because I
On 6/22/2011 1:32 AM, Paul Rubin wrote:
Terry Reedytjre...@udel.edu writes:
If the best C program for a problem takes 10 seconds or more, then
applying the same 1 minute limit to Python is insane, and contrary to
the promotion of good algorithm thinking.
The Euler problems
are not the
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
On Tue, Jun 21, 2011 at 1:48 PM, John Salerno johnj...@gmail.com wrote:
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
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
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 ?
[ ... ]
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
On 21-06-11 22:10, Irmen de Jong wrote:
[stuff]
I didn't read the last paragraph of John's message until just now, and
now realize that what I wrote is likely way too much information for
what he asked.
I'm sorry. Next time I'll read everything until and including the last
full stop.
Irmen
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
On Jun 21, 3:22 pm, Irmen de Jong ir...@-nospam-xs4all.nl wrote:
On 21-06-11 22:10, Irmen de Jong wrote:
[stuff]
I didn't read the last paragraph of John's message until just now, and
now realize that what I wrote is likely way too much information for
what he asked.
I'm sorry. Next time
On 21-6-2011 23:09, John Salerno wrote:
On Jun 21, 3:22 pm, Irmen de Jong ir...@-nospam-xs4all.nl wrote:
On 21-06-11 22:10, Irmen de Jong wrote:
[stuff]
I didn't read the last paragraph of John's message until just now, and
now realize that what I wrote is likely way too much information for
On Tue, Jun 21, 2011 at 3:09 PM, John Salerno johnj...@gmail.com wrote:
Don't worry, I was still unclear about what to do after reading all
the responses, even yours! But one thing that made me feel better was
that I wasn't having a Python problem as much as a *math* problem. I
changed my
On Jun 21, 4:41 pm, Ian Kelly ian.g.ke...@gmail.com wrote:
On Tue, Jun 21, 2011 at 3:09 PM, John Salerno johnj...@gmail.com wrote:
Don't worry, I was still unclear about what to do after reading all
the responses, even yours! But one thing that made me feel better was
that I wasn't having a
On Wed, Jun 22, 2011 at 7:48 AM, John Salerno johnj...@gmail.com wrote:
Thanks for the all the advice everyone. Now I'm on to problem #4, and
I'm stumped again, but that's what's fun! :)
So now that you've solved it, I'd like to see some fast one-liners to
do the job. (Since Python cares about
Oops, realized after posting that there's a bug in my code - it
returns 1 for a perfect square. Need another check in the 'while'
loop, thus:
On Wed, Jun 22, 2011 at 8:59 AM, Chris Angelico ros...@gmail.com wrote:
exec 600851475143; for (int i=2;iret;++i) while (ret%i==0 reti) ret/=i
while
On 6/21/2011 3:48 PM, John Salerno wrote:
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
2011/6/21 John Salerno johnj...@gmail.com:
However, even after reading the Wikipedia page about prime numbers and
trial division, I'm still a little unclear as to why the square root
of the number is the upper bound of the range you need to check.
--
There are likely be some more elaborated
Terry Reedy tjre...@udel.edu writes:
efficient implementation will allow a solution to be obtained on a
modestly powered computer in less than one minute.
If something really takes a minute in C,
allow yourself at least 10 minutes or even more with plain CPython.
No. The idea of the Euler
John Salerno johnj...@gmail.com writes:
However, even after reading the Wikipedia page about prime numbers and
trial division, I'm still a little unclear as to why the square root
of the number is the upper bound of the range you need to check.
Suppose p is the smallest divisor of n, and p
::sigh:: Well, I'm stuck again and it has to do with my get_factors
function again, I think. Even with the slight optimization, it's
taking forever on 20! (factorial, not excitement) :) It's frustrating
because I have the Python right, but I'm getting stuck on the math.
The problem:
What is the
John Salerno johnj...@gmail.com writes:
It's frustrating because I have the Python right, but I'm getting
stuck on the math
What is the smallest positive number that is evenly divisible by all
of the numbers from 1 to 20?
The answer is lcm [1,2,3, ... 20]. You can figure out how to
On 22/06/2011 02:21, John Salerno wrote:
::sigh:: Well, I'm stuck again and it has to do with my get_factors
function again, I think. Even with the slight optimization, it's
taking forever on 20! (factorial, not excitement) :) It's frustrating
because I have the Python right, but I'm getting
John Salerno wrote:
::sigh:: Well, I'm stuck again and it has to do with my get_factors
function again, I think. Even with the slight optimization, it's
taking forever on 20! (factorial, not excitement) :) It's frustrating
because I have the Python right, but I'm getting stuck on the math.
On Tue, Jun 21, 2011 at 4:30 PM, Terry Reedy tjre...@udel.edu wrote:
On 6/21/2011 3:48 PM, John Salerno wrote:
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
On Jun 21, 9:09 pm, Paul Rubin no.em...@nospam.invalid wrote:
John Salerno johnj...@gmail.com writes:
It's frustrating because I have the Python right, but I'm getting
stuck on the math
What is the smallest positive number that is evenly divisible by all
of the numbers from 1 to 20?
On Jun 21, 10:02 pm, Mel mwil...@the-wire.com wrote:
John Salerno wrote:
::sigh:: Well, I'm stuck again and it has to do with my get_factors
function again, I think. Even with the slight optimization, it's
taking forever on 20! (factorial, not excitement) :) It's frustrating
because I
On 6/21/2011 8:00 PM, Paul Rubin wrote:
Terry Reedytjre...@udel.edu writes:
efficient implementation will allow a solution to be obtained on a
modestly powered computer in less than one minute.
If something really takes a minute in C,
allow yourself at least 10 minutes or even more with plain
Terry Reedy tjre...@udel.edu writes:
If the best C program for a problem takes 10 seconds or more, then
applying the same 1 minute limit to Python is insane, and contrary to
the promotion of good algorithm thinking.
The Euler problems are all designed to be doable in 1 minute or less and
the
36 matches
Mail list logo
