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.