OraQA

The following is an interesting puzzle posted by Usenet rec-puzzles.org archive:

2 is prime, but 12, 22, .., 92 are not. Similarly, 5 is prime whereas 15, 25, .., 95 are not.
What is the next prime number which is composite when any digit is prefixed?

 variable input number
 exec :input := 20000;

———————————SQL SOLUTION————————–

SELECT min(next_num) result
FROM
(WITH data AS (
      SELECT LEVEL+1 num FROM dual
      WHERE LEVEL+1 <=:input
      CONNECT BY LEVEL <=:input),
      prime AS (
      SELECT num
      FROM data,
      (SELECT d1.num * d2.num as n2
       FROM data d1, data d2
       WHERE  d1.num <= d2.num
       AND d1.num <= sqrt(:input)
       AND d1.num * d2.num <= :input
      )
      WHERE num = n2(+)
      AND n2 IS NULL )
 SELECT next_num
 FROM
 (SELECT to_number(prefix||num) pre_num, num next_num
   FROM
   (SELECT num
      FROM prime
    WHERE to_number(9||num) <=:input
    AND num > 5), (SELECT LEVEL prefix FROM dual CONNECT BY LEVEL <=9)
    ), (SELECT num FROM prime)
   WHERE num(+) = pre_num
   AND  num IS NULL
   GROUP BY next_num
   HAVING count(*) = 9
 );

 

    RESULT
-------------
       149

Filed under SQL. Follow any responses to this entry through this RSS 2.0 feed.