puzzleup2012谜题，请用SQL或PLSQL解答

newkid

#14
Full Prime Number

All the numbers that can be read with two or more adjacent digits inside a prime number are also prime numbers. What is the greatest number having this property?

Exampe:6173 is such a number. Because 61, 17, 73, 617, 173 and 6173 are prime numbers

在一个素数中，所有相邻两位或两位以上的数字也构成了素数。具备这种属性的最大素数是多少？
例如，6173就是这样的一个数，因为 61, 17, 73, 617, 173 和 6173 都是素数。

具备这种条件的素数很少，所以是很容易找的。

lastwinner

newkid 发表于 2012-10-25 02:33
#14
Full Prime Number

两位素数做个connect by，就可以找出候选数了
当然，还是用递归来得好点，可以提前过滤掉很多不合格的解

用pl/sql等过程语言的话，从两位素数开始，在后面添1/3/7/9，看看新形成的数字是否满足要求，不满足的就筛掉，满足的就继续往下找

最大的数能有几位呢？
显然，第一位可以是奇数也可以是偶数，我们先考察第二位及之后的数字
后续任何一位上的数字只能是1/3/7/9之一，而3和9是3的倍数，因此不可能连续出现，否则就可以被3整除了，而1和7的总共出现次数肯定不能超过2次，因为二者除以3都余1，所以一旦总共出现3次，那么后面的几位数一定可以被3整除
所以从第二位开始，最多可以有5位数，用正则表达式表示就是
[39][17][39][17][39]
如此一来，第一位必然不能是3/6/9，而如果是1/4/7，则最多只能有4位，即[147][39][17][39]，如果是2/5/8，则最多就两位，即[258][39]
如果第一位没有，或者说第一位是0，那么最多就可能是5位数，由于第一位可以是偶数，所以5位数可能是
[369][17][39][17][39]

lastwinner

lastwinner 发表于 2012-10-25 03:08
两位素数做个connect by，就可以找出候选数了
当然，还是用递归来得好点，可以提前过滤掉很多不合格的解 ...

由于题目已经给出了6173，所以更大的数就可能是（仅从可被3整除和不是偶数来看）
[7][39][17][39]，总共8种可能
[69][17][39][17]，总共16种可能
[69][(17)|(71)][39]，总共8种可能
[369][17][39][17][39]，总共48种可能

如果在上述可能里找不到满足条件的数或者找到的比6173小，那么，最大的数就是6173

自己人肉到一个最大的四位数9719，猜测这就是最大数了
9737和9731都不是素数，所以9开头的不可能凑成5位数，也不可能大于9719
31开头的也不靠谱，37973很可惜是个合数
再考察6开头的，61开头的没戏，67开头的67379是合数，很可惜
所以我认为，最大的满足条件的数就是9719了

newkid

61979 ?

lastwinner

newkid 发表于 2012-10-25 04:04
61979 ?

昨天我做这个题的时候，用到的一个辅助网页
http://zh.nl.numberempire.com/61979

lastwinner

979=11 * 89，所以我才说61开头的没戏

lastwinner

another辅助页：http://zhidao.baidu.com/question/5644722.html
查表还是要快很多
剩下的诸如3131和91肯定是合数，这个是人脑的结果

newkid

花花的肉果然强大：


WITH t0 AS (
    SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (100000)/2-1-1
    ),
t as(SELECT rn from t0
      where mod(rn,3)<>0
            and mod(rn,5)<>0
            and mod(rn,7)<>0
    )
,p AS (
SELECT TO_CHAR(rn) n,LENGTH(rn) len
   FROM (SELECT rn from t
         MINUS
         SELECT t1.rn * t2.rn
           FROM t t1, t t2
         WHERE t1.rn <= t2.rn
               AND t1.rn BETWEEN 11 AND (SELECT SQRT(100000) FROM DUAL)
               AND t1.rn * t2.rn <100000
       )
WHERE rn>10
)
,t2 AS (
SELECT p1.n||substr(p2.n,2) AS n
  FROM p p1, p p2, p
WHERE p1.len=2 AND p2.len=2
       AND SUBSTR(p1.n,2)=substr(p2.n,1,1) AND p1.n||substr(p2.n,2) =p.n
)
,t3 AS (
SELECT t21.n||substr(t22.n,3) AS n
  FROM t2 t21,t2 t22,p
WHERE SUBSTR(t21.n,2)=substr(t22.n,1,2) AND t21.n||substr(t22.n,3)=p.n
)
,t4 AS (
SELECT t31.n||substr(t32.n,4) AS n
  FROM t3 t31,t3 t32,p
WHERE SUBSTR(t31.n,2)=substr(t32.n,1,3) AND t31.n||substr(t32.n,4)=p.n
)
SELECT * FROM t4;

no rows selected

可见5位数的没有答案，改用4位：

WITH t0 AS (
    SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (100000)/2-1-1
    ),
t as(SELECT rn from t0
      where mod(rn,3)<>0
            and mod(rn,5)<>0
            and mod(rn,7)<>0
    )
,p AS (
SELECT TO_CHAR(rn) n,LENGTH(rn) len
   FROM (SELECT rn from t
         MINUS
         SELECT t1.rn * t2.rn
           FROM t t1, t t2
         WHERE t1.rn <= t2.rn
               AND t1.rn BETWEEN 11 AND (SELECT SQRT(100000) FROM DUAL)
               AND t1.rn * t2.rn <100000
       )
WHERE rn>10
)
,t2 AS (
SELECT p1.n||substr(p2.n,2) AS n
  FROM p p1, p p2, p
WHERE p1.len=2 AND p2.len=2
       AND SUBSTR(p1.n,2)=substr(p2.n,1,1) AND p1.n||substr(p2.n,2) =p.n
)
,t3 AS (
SELECT t21.n||substr(t22.n,3) AS n
  FROM t2 t21,t2 t22,p
WHERE SUBSTR(t21.n,2)=substr(t22.n,1,2) AND t21.n||substr(t22.n,3)=p.n
)
SELECT * FROM t3;

N
-----------------------
9719
6131
3137
1373
6173
3797
6197

7 rows selected.

Elapsed: 00:00:00.89

最大确实是9719。

〇〇

udfrog 发表于 2012-10-18 10:16
嗯，差不多

看不懂
SQL> set timi on
SQL> with df as (
  2  select (rownum+1)*(rownum+1) df from dual connect by rownum<=20),
  3  t as (
  4  select rownum f from dual connect by rownum<=1000),
  5  tmp as (
  6  select        min(df*f) keep (dense_rank first order by df*f) r, row_number() over (order by df*f) rn
  7  from        df, t
  8  group by df*f)
  9  select        min(a.r)-2
10  from        tmp a, tmp b
11  where        a.r=b.r+4
12  and        a.rn=b.rn+4;

MIN(A.R)-2
----------
       846

已用时间:  00: 00: 00.07

udfrog

〇〇 发表于 2012-10-26 12:26
看不懂
SQL> set timi on
SQL> with df as (

因为5个数连续，所以
a.r=b.r+4
and        a.rn=b.rn+4;