Ward Pond's SQL Server blog

Ruminating on issues pertinent to the design and development of sound databases and processes under Microsoft SQL Server 2008, SQL Server 2005, and SQL Server 2000 (while reserving the right to vent about anything else that's on my mind)

A "Kobiyashi Maru" On The Prime Number Front?

A "Kobiyashi Maru" On The Prime Number Front?

  • Comments 2
  • Likes

No less a figure than Louis Davidson has weighed in on the Prime Number Challenge.  I left a comment on his blog last week which has yet to be published, so I'll respond to Louis here.

Here's the salient part of Louis' post: 

A friend blogger wrote an article about how to return prime numbers from SQL here: http://sqlservercode.blogspot.com/2006/09/return-all-78498-prime-numbers-between.html.  Frankly, I was impressed by some of the responses I saw around about this topic.  For example, this post: http://blogs.technet.com/wardpond/archive/2006/09/23/458591.aspx and these too: http://robfarley.blogspot.com/2006/09/primes.html, and http://robfarley.blogspot.com/2006/09/more-on-primes.html.  But the answer I came up with is far faster than any of theirs for a production system (not nearly as cool, and takes far less brains, lucky for me.)

create table primeNumbers

(

    i   int primary key

)

insert into primeNumbers select 2

insert into primeNUmbers select 3
...

Once this code is done and stored, you never have to recalculate, unless someone comes up with some new prime numbers, which is pretty much unlikely.  So if you need a prime number, the value is there and ready to use.

First of all, Louis, many thanks for your kind words. 

While I agree that your alternative might run faster than Hugo's, Denis', or Rob's syntax, there's still the small matter of generating the INSERT statements.  The solution you've proposed requires previous knowledge of the prime numbers -- how else can we generate the appropriate INSERTs?

Since the purpose of the exercise is to build this list, I don't think we can use a syntax which presupposes that the list has already been generated.  We'd essentially be rephrasing the problem, much like Kirk's response to the Kobiyashi Maru test (the no-win scenario) in the first Star Trek movie.

So, from my perspective, straight INSERT statements don't cut the mustard in the Prime Number challenge.  If you feel differently, please let me know!

     -wp

UPDATE (18 October 2006): Louis has updated his post to more clearly reflect his contention that we'd only ever build this list once.  On this point, we are in complete agreement.  Thanks for the clarification, Louis.

Comments
  • Yeah, I probably should have more clear.  My point was with this part of the post:

    create table primeNumbers

    (

       i   int primary key

    )

    And was really off the topic of generating prime numbers (my attempts fell down bigtime on that) and was just noting that no matter how fast the algorithm was, that in a production system if you regularly need a set of prime numbers, you would never want to calculate them for every use.  You would build the table once and never look back since it would be rediculous to waste CPU on this every single time you need a prime number between 12000 and 13000.  

    That is what would be faster, the usage, not the loading.  I am going to edit the posts right now to reflect that.  Thanks for noting this.

  • Thanks for the clarification, Louis.  I concur with your point completely and mentioned it in my first post -- we'd run whatever code we've got once to populate a table, and then query the table thereafter.  The tuning of the query to build the table is just for fun and bragging rights :), although I've been thinking that a UDF to diagnose primacy or lack thereof in a single integer might be interesting..

        -wp

Your comment has been posted.   Close
Thank you, your comment requires moderation so it may take a while to appear.   Close
Leave a Comment