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 probl
Mel 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 small factors
On 6/22/2011 1:32 AM, Paul Rubin wrote:
Terry Reedy 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 only algorithm probl
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 Wed, Jun 22, 2011 at 6:01 AM, Anny Mous 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/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 fa
On Wed, Jun 22, 2011 at 10:01 PM, Anny Mous 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 one of those befor
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, a
On Tue, Jun 21, 2011 at 11:58 PM, Chris Torek 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, e.g.:
This
Chris Torek 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 iterto
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 gener
Terry Reedy 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 Euler project s
On 6/21/2011 8:00 PM, Paul Rubin wrote:
Terry Reedy 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.
On Jun 21, 10:02 pm, Mel 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 have the Pytho
On Jun 21, 9:09 pm, Paul Rubin wrote:
> John Salerno 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, ..
On Tue, Jun 21, 2011 at 4:30 PM, Terry Reedy 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 difficult prob
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 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 stu
John Salerno 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 implement
lcm.
Th
::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 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 > sqrt(n).
("Diviso
Terry Reedy 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 problems is
2011/6/21 John Salerno :
> 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 proofs, but it s
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 o
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 wrote:
> exec 600851475143; for (int i=2;ii) ret/=i
>
> while not ret%i and ret>i:
Definitely room for im
On Wed, Jun 22, 2011 at 7:48 AM, John Salerno 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 whitespace, it mi
On Jun 21, 4:41 pm, Ian Kelly wrote:
> On Tue, Jun 21, 2011 at 3:09 PM, John Salerno 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 *mat
On Tue, Jun 21, 2011 at 3:09 PM, John Salerno 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 get_factors functio
On 21-6-2011 23:09, John Salerno wrote:
> On Jun 21, 3:22 pm, Irmen de Jong 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 a
On Jun 21, 3:22 pm, Irmen de Jong 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 I'll read everythin
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 g
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
-
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
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
On Tue, Jun 21, 2011 at 1:48 PM, John Salerno 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 range(2, n //2), but
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 wor
36 matches
Mail list logo
