星期三, 6月 05, 2013

[Challenge] 統計回文質數

Beyond Relational Challenge 7

This challenge is to test the logical ability and does not have any resemblance with real time problem. The task is to generate the palindrome primes from 10 to 1000 and count the number of occurrences of each digit in them

A number that reads the same from left to right and vice versa is a palindrome number, for example 121 or 65456. Primes numbers are those that are divisible only by 1 and the number itself, for example 2 or 5.
  • Sample Data
根據題目來產生所需要數字
  • Expected Results
PalindromPrimes 0 1 2 3 4 5 6 7 8 9
--------------- -- -- -- -- -- -- -- -- -- --
11              - 2 - - - - - - - -
101             1 2 - - - - - - - -
131             - 2 - 1 - - - - - -
151             - 2 - - - 1 - - - -
181             - 2 - - - - - - 1 -
191             - 2 - - - - - - - 1
313             - 1 - 2 - - - - - -
353             - - - 2 - 1 - - - -
373             - - - 2 - - - 1 - -
383             - - - 2 - - - - 1 -
727             - - 1 - - - - 2 - -
757             - - - - - 1 - 2 - -
787             - - - - - - - 2 1 -
797             - - - - - - - 2 - 1
919             - 1 - - - - - - - 2
929             - - 1 - - - - - - 2
11 is a palindrome prime number and hence it is listed in the output. 11 has the number "1" twice and therefore the column "1" shows 2. Another palindrome prime, "101" has one zero and two ones. That is why the column "0" shows 1 and the column "1" shows 2.
  • Rules
    1. The code should run in SQL SERVER 2005 and later versions.
    2. The code should generate the palindrome prime numbers. It should not read from a static table/cte/view.
    3. Output should be sorted by the first column(Palindrome Primes) in ascending order.

  • 個人解法
;
WITH Number AS
(
  SELECT 1 AS Number
  UNION ALL
  SELECT Number + 1 
  FROM Number
  WHERE Number < 1000
)
,
CTE AS 
(
  SELECT Number , 1 AS Location
  FROM Number
  WHERE CAST(Number AS varchar(4)) = REVERSE(CAST(Number AS varchar(4))) -- 判斷回文
    AND Number > 10 -- 根據題目只計算 10 至 1000 之間的回文質數
  UNION ALL
  SELECT NumBer , Location + 1
  FROM CTE
  WHERE Location < LEN(CAST(Number AS varchar(4)))
)
SELECT 
  Number AS PalindromPrimes ,
  ISNULL(NULLIF(CAST([0] AS varchar(1)),'0'),'-') AS [0],
  ISNULL(NULLIF(CAST([1] AS varchar(1)),'0'),'-') AS [1],
  ISNULL(NULLIF(CAST([2] AS varchar(1)),'0'),'-') AS [2],
  ISNULL(NULLIF(CAST([3] AS varchar(1)),'0'),'-') AS [3],
  ISNULL(NULLIF(CAST([4] AS varchar(1)),'0'),'-') AS [4],
  ISNULL(NULLIF(CAST([5] AS varchar(1)),'0'),'-') AS [5],
  ISNULL(NULLIF(CAST([6] AS varchar(1)),'0'),'-') AS [6],
  ISNULL(NULLIF(CAST([7] AS varchar(1)),'0'),'-') AS [7],
  ISNULL(NULLIF(CAST([8] AS varchar(1)),'0'),'-') AS [8],
  ISNULL(NULLIF(CAST([9] AS varchar(1)),'0'),'-') AS [9]
FROM
  (
    SELECT 
      E.Number , 
      SUBSTRING(CAST(E.Number AS varchar(4)),Location,1) AS String 
    FROM CTE AS E
      JOIN 
        (
          SELECT X.Number
          FROM Number AS N 
            CROSS JOIN Number AS X
          WHERE X.Number % N.Number <> 0 
            AND X.Number > 1
            AND N.Number > 0 
            AND N.Number < X.Number
            AND X.Number % 2 <> 0
          GROUP BY X.Number
          HAVING (X.Number - COUNT(*)) = 2
        ) AS R ON E.Number = R.Number
  ) AS P 
PIVOT 
  (
    COUNT(String) FOR String IN ([0],[1],[2],[3],[4],[5],[6],[7],[8],[9])
  ) AS PV
ORDER BY Number
OPTION (MAXRECURSION 1000)
質數判斷部分是直接拿網路上的 T-SQL 語法來應用。

    沒有留言:

    張貼留言