Iirc, Python periodically cleans memory of bits & pieces that are no longer
being used. I periodically do something stupid -- I mean experimental --
and end up with a semi-locked up system. Sometimes it comes back,
sometimes everything after that point runs very slowly, etc.
I just saw where I cou
I'm also happy to note that the sieve I adapted from Jorge generates a list
of primes the same length as yours, which would seem to imply it's correct,
and in 33s, though since it's timed by a different mechanism that may not
mean anything...
On Tue, Jan 7, 2014 at 10:36 PM, Keith Winston wrote:
Hey Steven,
That's a cool primes module, I'm going to look that over more carefully. I
can see that you've thought through this stuff before ;)
And yeah, I'd like to see your Stopwatch code... I haven't looked at "with"
yet, that's interesting. As usual, I don't totally get it...
Keith
_
On Tue, Jan 07, 2014 at 01:32:51PM -0800, Danny Yoo wrote:
> Hi Keith,
>
> Ah, good point. I did not realize that we could use a sqrt() to get a
> good upper bound on what primes we can consider. That cuts down on
> the size of the search space enormously. Ok, I take my objection back
> then.
>
oops, I'm sorry I didn't realize Danny's message to me was private, but
you're right that's better than publishing this right out.
Also: although the sqrt(n) algorithm worked to solve the problem, it isn't
actually correct. There are cases in which it will fail, many in fact.
Oops. One would need
That makes total sense now. I was just curious as to why it didn't output
the arbitrary delimiter in the list, or if there was a specific reason for
it.
On Sat, Jan 4, 2014 at 10:03 PM, Danny Yoo wrote:
> One of the common cases for split() is to break a line into a list of
> words, for examp
On 07/01/14 21:22, Keith Winston wrote:
Note that his code doesn't really (need to) create a sieve of
Eratosthenes all the way to n, but only to sqrt(n). It then tests for
divisibility.
I'm not sure what you mean here.
His algorithm was using an array of booleans to indicate whether a
number
For reference, Keith's referring to a solution I wrote up and sent to
him privately. The solution is on a private gist.github.com, since I
want to avoid posting complete Project Euler solutions on a public
forum. If you're interested, you can email me privately.
Be well!
___
Sorry for the blank message.
I was just going to say that I fixed my version of Eratosthenes' algorithm,
but Danny's is still faster in all cases.
Also, Jorge: I hope it's obvious that I'm kidding around, I wouldn't want
you to feel uncomfortable with asking your questions just because I'm being
On Tue, Jan 7, 2014 at 5:45 PM, Keith Winston wrote:
> Hey Danny,
>
> I think you could use the same sqrt(n) on your algorithm to reduce the
> search space. I think you could also increment n += 2 to skip even numbers,
> the simplest of sieves.
>
> I think the sieve concept is based on the idea t
Hey Danny,
I think you could use the same sqrt(n) on your algorithm to reduce the
search space. I think you could also increment n += 2 to skip even numbers,
the simplest of sieves.
I think the sieve concept is based on the idea that adding is much less
intensive than dividing, so creating the si
In fact, I just used it to solve a number 3 orders of magnitude larger than
600851475143, the number from prob 3. It took 12s. I hardly dare go further
than that... I'm not arguing that there's a big list being built in there...
Oops, I dared. 5 orders of magnitude bigger crashes my machine.
Oops
Hi Keith,
Ah, good point. I did not realize that we could use a sqrt() to get a
good upper bound on what primes we can consider. That cuts down on
the size of the search space enormously. Ok, I take my objection back
then.
(That being said, I'm fairly certain that this problem can be solved
in
um, I used his code, slightly fine-tuned it, and got the solution in
.35 seconds (running time, not fine-tuning time ;). On my dinky old
notebook. So I'm inclined to believe it is possible... Though perhaps my
sense of what "fine-tuning" entails doesn't mesh with yours... spoiler
alert, more be
Hi Keith,
I have disagree with the assessment that fine-tuning will result in a
solution. The standard Sieve of Erathothenes approach is _not
possible_ on standard computers due to the memory requirement estimate
that eryksun has presented. The point of some of the problems on
Project Euler is t
I think your approach is fine, you might need to fine tune your algorithm.
hint below.
if you want it: is_p doesn't need to be nearly as big as you specify. There
are a couple other minor problems.
___
Tutor maillist - Tutor@python.org
To un
As eryksun points out, the memory requirements for a sieve this large
make that approach untenable.
For this particular problem, brute force factoring the number can
work. That particular number has primes that are much smaller than
the number itself: you should be able to do a simple range loop
I had heard of Project Euler long ago, but completely forgotten it. It
looks fun!! Thanks for reminding me of it.
Keith
On Tue, Jan 7, 2014 at 5:58 AM, eryksun wrote:
> On Tue, Jan 7, 2014 at 4:49 AM, Jorge L. wrote:
> >
> > When i test that script against 600851475143 I get the following err
--
On Mon, Jan 6, 2014 1:01 PM CET eryksun wrote:
>On Mon, Jan 6, 2014 at 5:59 AM, Rafael Knuth wrote:
>>
>> does anyone know how to activate virtualenv in Windows?
>> Virtualevwrapper works great on Linux, maybe on Widows too:
https://pypi.python.org/pypi/
On Mon, Jan 06, 2014 at 04:57:38PM +0800, Amrita Kumari wrote:
> Hi Steven,
>
> I tried this code:
>
> import csv
> with open('file.csv') as f:
> reader = csv.reader(f)
> for row in reader:
> print(row)
> row[0] = int(row[0])
>
> up to this extent it is ok; it is ok i
On Tue, Jan 7, 2014 at 4:49 AM, Jorge L. wrote:
>
> When i test that script against 600851475143 I get the following error
You're trying to create a list with over 600 billion items.
sys.maxsize is a bit over 2 billion for 32-bit CPython, but switching
to 64-bit won't help unless you have a few t
On 07/01/14 09:49, Jorge L. wrote:
I'm working through Project Euler problems, now I'm at problem 3. I did
an implementation of the shieve of Erastothenes to find the prime
numbers less than a given number. Then I run a divisibility test over
those prime numbers to find the largest prime factor o
I'm working through Project Euler problems, now I'm at problem 3. I did an
implementation of the shieve of Erastothenes to find the prime numbers less
than a given number. Then I run a divisibility test over those prime
numbers to find the largest prime factor of that given number. Here's the
code:
23 matches
Mail list logo
