# SQL Puzzle – Prime Numbers

9September 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.

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)

Looks like wordpress sanitized the code

Numbers.Number % 2 0 OR Numbers.Number =

should be

Numbers.Number % 2 < > 0 OR Numbers.Number =

Fixed and modified to work in a case-sensitive environment 🙂 Nice job! It’s still limited by the size of spt_numbers though, right?

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

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.

A bit off-topic here, but I’m pretty sure someone else made that word up, too.

This is really cool! I’ve never seen a prime calculator written in SQL. Neat!

WITH numbers0

AS (SELECT 3 AS NUMBER

UNION ALL

SELECT NUMBER + 2 AS NUMBER

FROM numbers0

WHERE NUMBER < 1000)

, numbers

AS (SELECT NUMBER

FROM numbers0

UNION ALL

SELECT 2 AS NUMBER)

, primes

AS (SELECT ROW_NUMBER() OVER (ORDER BY NUMBER) AS SEQ

, n1.NUMBER

FROM numbers n1

WHERE NOT EXISTS (SELECT n2.NUMBER

FROM numbers n2

WHERE n1.NUMBER % n2.NUMBER = 0

AND n2.NUMBER <= SQRT(n1.NUMBER)))

SELECT SEQ

, NUMBER AS PRIME

FROM primes

ORDER BY 1

OPTION (MAXRECURSION 0)

;