Interview Question - Write a Query to list the Prime numbers between 1 to 100

This one is something that was just tossed-up at me by my team lead. Honestly, it took me few seconds to recall what Prime Number is. And when I knew what I need to find, I started thinking about the logic to do it..

Prime Number - A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself. In simple words, any Positive Number number which is divisible by Itself or 1. 

I could think of following ways to achieve it

• Divide given number by the numbers ranging from 2 to "that number" - 1. If reminder is 0 for either of the division then it's not a Prime number. If reminder is > 0 for all the divisions then it's a prime number. To carry out this division either Loop or cursor can be used. 

For Exp : To check whether 13 is a prime number or not. Begin dividing it with 2 first check for reminder if > 0 then divide by 3 else break loop and conclude its not a prime number. With 3 if reminder > 0 then divide by 4 else break loop and conclude.. continue likewise for rest of the numbers ,4,5,6,7,8,9,10,11,12.

• First Divide number by 2 this will give you the number which is half of the number that you are inspecting and that would be the last number which would be able to divide the number in question. Then follow First logic. 

For Exp : To check whether 13 is a prime number or not. First do 13/2 = 6.5 round it to 6. Start following process defined in first logic from 3 but till 6 only. this is because  7 > 6.5 (half of the number) so there is no way any number > 6.5 would be able to give reminder = 0  by dividing 13.

Second option is better choice than first as it is evident that we will have to do fewer divisions. 

Then I searched over net and came across another logic of using square root . And I decided to design my query to utilize square root logic.

Since I had to list all the prime numbers between 1 to 100 I added extra conditions (not to consider numbers divisible by 2,3 and 5 ) which eliminated group of numbers from the check even before we start looping. 

Given below is the script that I had designed.

DECLARE @TAB TABLE(ID TINYINT)

;WITH TabPopulate AS(SELECT 1 AS ID
UNION ALL
SELECT ID +  1 FROM TabPopulateWHERE ID <= 99)INSERT INTO @TABSELECT * FROM TabPopulate
--SELECT * FROM @TAB
;WITH CTE AS(SELECT ID,CONVERT(INT,CEILING(SQRT(ID))) AS SQRT,CONVERT(INT,CEILING(SQRT(ID))) AS sqr, 2 AS stptFROM @TABWHERE ((ID%2 != 0) OR ID = 2) AND ((ID%3 != 0) OR ID = 3) AND ((ID%5 != 0) OR ID = 5)

  UNION ALL

  SELECT ID,SQRT,ID%stpt,stpt + 1FROM CTEWHERE stpt  <= SQRT)SELECT IDFROM CTEWHERE sqr != 0 AND ID > 1
EXCEPT

SELECT IDFROM CTE WHERE sqr = 0 AND ID <> 2