SQL Puzzle – Prime Numbers

6

September 27, 2017 by Kenneth Fisher

My goal here is to have something fun (and hopefully educational/thinky) (and yes, I did just make up the word thinky, live with it) at the end of each month. So this month it’s a puzzle. Calculate the first 10 prime numbers.

Definition of a prime number:

A Prime Number can be divided evenly only by 1, or itself. And it must be a whole number greater than 1.

Goals (since I can’t think of any real rules)

  • Should be able to easily extend the solution past 10. i.e. if I asked you to come up with the first 20 prime numbers it would require minimal changes to your code.
  • This is T-SQL. Set based is always preferable over RBAR (loops). FYI this can be trickier than it sounds since technically things like recursive CTEs are actually RBAR behind the scenes (as I understand it).
  • Speed! Speed is important. Prime numbers are one of those things that can get pretty large pretty quickly. Maybe your method will be the one the scientists use going forward to calculate prime numbers. 🙂
  • The simpler the code the better. If you aren’t a junior DBA, write it so that one can read it.
  • Comments as necessary. If your code is anything above junior level then it needs comments. It’s good to get into the habit even in simple code.

 


Here is my solution:

Using a numbers table (that I got from Aaron Bertrand’s (b/t) post http://sqlblog.com/blogs/adam_machanic/archive/2006/07/12/you-require-a-numbers-table.aspx

SELECT TOP (10) Number
FROM Numbers
WHERE Numbers.Number > 1 -- We only want numbers > 1
  AND NOT EXISTS (
	SELECT 1 FROM Numbers N2
	WHERE N2.Number > 1 -- We only want numbers > 1
	  -- We only need to test numbers less than the current number
	  AND Numbers.Number > N2.Number
	  -- Check to see if there are any numbers that evenly divide in.
	  AND Numbers.Number % N2.Number = 0
	)

And I get the answer: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Now the down side here is that my numbers table has to be big enough to cover any number I’m going to test. Eventually that could require a pretty large numbers table. I’ll leave it to you to decide if that’s important or not.

6 thoughts on “SQL Puzzle – Prime Numbers

  1. denisgobo says:

    Here is a half baked Sieve of Eratosthenes approach. Your numbers table doesn’t need to have anything divisible by 2,3,5 or 7.. so it can be 80% smaller.

    Sample code you can run

    — create a derived table with numbers above 10
    — strip out anything divisible by 2,3,5,7 but not 2,3,5,7 itself
    WITH numbers as (SELECT number
    FROM master..spt_values numbers
    WHERE type =’P’
    AND number > 1 — We only want numbers > 1
    AND (numbers.number % 2 <> 0 OR numbers.number = 2)
    AND (numbers.number % 3 <> 0 OR numbers.number = 3)
    AND (numbers.number % 5 <> 0 OR numbers.number = 5)
    AND (numbers.number % 7 <> 0 OR numbers.number = 7) )

    SELECT TOP (300) number from numbers
    WHERE NOT EXISTS(SELECT 1 FROM numbers N2
    — We only need to test numbers less than the current number
    WHERE numbers.number < N2.number
    — Check to see if there are any numbers that evenly divide in.
    AND numbers.number % N2.number = 0)

  2. Ben Kubicek says:

    You know prime numbers are never even, so that could also limit what you need in your table and speed things up.

  3. deroby says:

    One small remark: You shouldn’t be doing SELECT TOP n without an ORDER BY… you’ll get 10 prime numbers here, but theoretically it might be ANY 10 prime numbers, not necessarily the first 10.

    Since I don’t really like rCTE’s I tried to do the same using a loop where I delete the multiples of a given number and then go on to the next number etc.. works remarkably well!

    For fun I added the ‘pre-filtereing’ as suggested by @denisgobo but IMHO that’s cheating =) Then again, it does wonders for the looped version!

    (I did simplify things to ‘give me all the primes up 50.000, you could add TOP n again but I think the net-effect will be the same)

    I was pretty pleased with the result as the looped version was twice as fast as the rCTE version. Then I got smart and realized I could optimize things by limiting the calculations to the square root of the number we’re examining. Turns out the rCTE takes the lead again performance wise, but (using the filtered version) it’s a close call =)

    https://www.dropbox.com/s/thw5atbg9gl08zc/prime%20numbers.sql?dl=0

    PS: I still don’t like rCTE’s =)

    • Nice! I really like that method! I’m a firm believer in known all the tools, use all the tools where appropriate 🙂 Generally (IMHO) the problem with things like rCTEs is that people use them poorly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 2,135 other followers

Follow me on Twitter

ToadWorld Pro of the Month November 2013
%d bloggers like this: