Re^2: ulam's spiral too slow


Think about Loose Coupling
	PerlMonks

Re^2: ulam's spiral too slow

by grinder (Bishop)

on Apr 15, 2007 at 20:28 UTC ( [id://610224]=note: print w/replies, xml )

Need Help??

in reply to Re: ulam's spiral too slow
in thread ulam's spiral too slow

you only need to be looking at all values between 2 and sqrt(N)

I was about to tick you off, for not suggesting examining only odd numbers, but in fact your code does exactly that. Nonetheless, the fact that you are caching previously discovered primes admits an elegant optimisation:

you only need to be looking at all prime numbers between 2 and sqrt(N).

Retooling your most excellent code is left as an exercise to the reader :)

• another intruder with the mooring in the heart of the Perl

Comment on Re^2: ulam's spiral too slow

Replies are listed 'Best First'.

Re^3: ulam's spiral too slow
by liverpole (Monsignor) on Apr 15, 2007 at 20:46 UTC

grinder

My laziness in not optimizing it further has been revealed.

As for counting by twos, I certainly could claim that my background gets the credit (I was a mathematics major), but I have to confess that many years ago I was the victim of a similar faux pas.

I was taking a Pascal course in college (my first structure programming language -- best language ever -- until I learned "C" a few years later). The term project I had chosen was to create a program that generated patterns from prime numbers. I wrote a similar is_prime subroutine which counted by ones, and a friend who looked at my code said "you realize of course...". Whoops!

s''(q.S:$/9=(T1';s;(..)(..);$..=substr+crypt($1,$2),2,3;eg;print$..$/

[reply]
[d/l]

In Section Seekers of Perl Wisdom