SQL Puzzle | The Circular Prime Numbers Puzzle

This question was asked to one of friend. Here you have to find out circular prime number upto certain input number.

What is Circular Prime Number – A circular prime number is a number that remains prime on any cyclic rotation of its digits. Any one-digit prime is circular by default. Thus, the circular one-digit primes are: 2, 3, 5 and 7.

For multi-digit numbers, the digits can only consist of the numbers 1, 3, 7 and 9, since any even digit will eventually be rotated to the unit’s place and make the number even, and any number ending with 5 is divisible by the circular prime number 5.

Please check out the sample input values and sample expected output below.

Sample Input

DECLARE @CicularPrimesUpto AS BIGINT = 100

Expected Output

2
3
5
7
11
13
17
31
37
71
73
79
97

Script

Use below script to create table and insert sample data into it.

 ```-- DECLARE @CicularPrimesUpto AS BIGINT = 100 -- ```

Rules/Restrictions

The solution should be should use “SELECT” statement or “CTE”.
 ``` -- DECLARE @CicularPrimesUpto AS BIGINT = 100 IF OBJECT_ID('tempdb..#baseTable') IS NOT NULL DROP TABLE tempdb..#baseTable IF OBJECT_ID('tempdb..#Looper') IS NOT NULL DROP TABLE tempdb..#Looper IF OBJECT_ID('tempdb..#Pawan') IS NOT NULL DROP TABLE tempdb..#Pawan IF OBJECT_ID('tempdb..#Pawan1') IS NOT NULL DROP TABLE tempdb..#Pawan1 CREATE TABLE #Pawan( a INT ) CREATE TABLE #Pawan1( original INT , a INT , t INT ) --Get Base PrimeNumber , Remove if prime numbers contains digits like 0, 2, 4, 6, 8, or 5 as they are not circular primes SELECT n INTO #baseTable FROM ( SELECT n , CASE WHEN ( n like '%%' ) AND LEN(n) > 1 THEN 0 ELSE 1 END filter FROM ( SELECT DISTINCT n FROM Number num WHERE n >= 2 AND n <= @CicularPrimesUpto AND NOT EXISTS ( SELECT * FROM Number AS num1 WHERE num1.n > 1 AND num1.n < num.n AND num.n % num1.n = 0 ) )e )f WHERE filter = 1 SELECT * INTO #Looper FROM #baseTable WHERE LEN(n) >= 2 WHILE EXISTS ( SELECT TOP 1 1 FROM #Looper ) BEGIN DECLARE @ AS BIGINT SELECT TOP 1 @ = n FROM #Looper IF LEN(@) <= 7 BEGIN DECLARE @str AS VARCHAR(100) SET @str = CAST(@ AS VARCHAR(100)) DECLARE @cols AS VARCHAR(100) = '' IF OBJECT_ID('tempdb..#T') IS NOT NULL DROP TABLE tempdb..#T SELECT DISTINCT SUBSTRING(@str,NUMBER,1) n INTO #T FROM MASTER..spt_values WHERE number > 0 AND number <= LEN(@) SELECT @cols = @cols + CAST(r AS VARCHAR(10)) FROM ( SELECT DISTINCT CONCAT(', o',number,'.n') r FROM MASTER..spt_values WHERE number > 0 AND number <= (LEN(@)-1) )q DECLARE @ExecStr AS VARCHAR(1000) = '' SET @ExecStr = 'SELECT CAST(CONCAT( a.n' + @cols + ' ) AS INT) Combinations FROM #T a' SELECT @ExecStr = @ExecStr + r FROM ( SELECT DISTINCT CONCAT(' CROSS APPLY ( SELECT * FROM #T b' , number , ' WHERE ( b' , number, '.n' , ' <> a.n ) ', CASE WHEN number = 1 then '' WHEN number = 2 then ' AND ( b2.n <> o1.n )' WHEN number = 3 then ' AND ( b3.n <> o1.n ) AND ( b3.n <> o2.n ) ' WHEN number = 4 then ' AND ( b4.n <> o1.n ) AND ( b4.n <> o2.n ) AND ( b4.n <> o3.n ) ' WHEN number = 5 then ' AND ( b5.n <> o1.n ) AND ( b5.n <> o2.n ) AND ( b5.n <> o3.n ) AND ( b5.n <> o4.n ) ' WHEN number = 6 then ' AND ( b6.n <> o1.n ) AND ( b6.n <> o2.n ) AND ( b6.n <> o3.n ) AND ( b6.n <> o4.n ) AND ( b6.n <> o5.n ) ' END ,') o' , number ) r FROM MASTER..spt_values WHERE number > 0 AND number <= (LEN(@)-1) )p TRUNCATE TABLE #Pawan INSERT INTO #Pawan(a) EXEC (@ExecStr) INSERT INTO #Pawan1 SELECT @ , a , ( SELECT COUNT( DISTINCT n ) FROM Number num WHERE n = a AND NOT EXISTS ( SELECT * FROM Number AS num1 WHERE num1.n > 1 AND num1.n < a AND a % num1.n = 0 ) ) IsPrime FROM #Pawan END DELETE FROM #Looper WHERE n = @ END SELECT DISTINCT n CircularPrimeNumbers FROM ( SELECT * , SUM(t) OVER (PARTITION BY b.n) cnt FROM #baseTable b LEFT JOIN #Pawan1 p ON b.n = p.original )o WHERE cnt > 1 OR cnt is null IF OBJECT_ID('tempdb..#baseTable') IS NOT NULL DROP TABLE tempdb..#baseTable IF OBJECT_ID('tempdb..#Looper') IS NOT NULL DROP TABLE tempdb..#Looper IF OBJECT_ID('tempdb..#Pawan') IS NOT NULL DROP TABLE tempdb..#Pawan IF OBJECT_ID('tempdb..#Pawan1') IS NOT NULL DROP TABLE tempdb..#Pawan1 -- ```