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.
SQL Studies 
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)
;