Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re^2: ulam's spiral too slow

by grinder (Bishop)
on Apr 15, 2007 at 20:28 UTC ( #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

Replies are listed 'Best First'.
Re^3: ulam's spiral too slow
by liverpole (Monsignor) on Apr 15, 2007 at 20:46 UTC
    ++grinder, an excellent point.

    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!


Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://610224]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (3)
As of 2021-07-30 23:07 GMT
Find Nodes?
    Voting Booth?

    No recent polls found