OraQA

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

What is the smallest number that cannot be made prime by changing a single digit?

variable input number
exec :input := 10000;

————————SQL Solution—————————

SELECT min(not_prime_num) Min_Chang_A_digit_Not_Prime
FROM
(SELECT num,
        CASE WHEN num + 1 != lead(num) OVER (ORDER BY num)
             THEN (num +1) * 10 END AS not_prime_num
FROM
(SELECT DISTINCT trunc(num/10) as num
 FROM
 (WITH data AS (SELECT LEVEL+1 num FROM dual
                WHERE LEVEL+1 <=:input
                CONNECT BY LEVEL <=:input)
  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
  )
 )
)
WHERE not_prime_num IS NOT NULL;

MIN_CHANG_A_DIGIT_NOT_PRIME
---------------------------
                        200

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