用SQL求解欧拉计划425题

newkid · 发表于 2017-2-25 00:34

lastwinner 发表于 2017-2-24 14:27
这段其实可以简化为
and substr(p2.n,-length(p2.n-p1.n),1)
>substr(p1. ...

对，我也就是想取非零的位数，多绕了一圈。
我怀疑我的PAIRS表是不是不完整，你们用其它办法生成数据然后核对一下？

〇〇 · 发表于 2017-2-25 07:17

newkid 发表于 2017-2-25 00:34
对，我也就是想取非零的位数，多绕了一圈。
我怀疑我的PAIRS表是不是不完整，你们用其它办法生成数据然 ...

pe论坛上的答案
11
101
103
107
109
1009
1013
1019
1021
1031
1033
1039
1049
1051
1061
1063
1069
1087
1091
1093
1097
1117
1201
1511
2003
2011
2017
2027
2029
2053
2221
2309
2333
3001
3023
3037
3121
4133
4363
5077
6043
6841

newkid · 发表于 2017-2-25 09:41

1013难道不是亲戚吗？
3,13,131,101,1013
同理还有1019，等等。

〇〇 · 发表于 2017-2-25 10:02

newkid 发表于 2017-2-25 09:41
1013难道不是亲戚吗？
3,13,131,101,1013
同理还有1019，等等。

13,131
只能在左边增减数字

newkid · 发表于 2017-2-25 11:08

〇〇发表于 2017-2-25 10:02
13,131
只能在左边增减数字

规则不清楚，早知道就很好办了。

declare
f number;
begin
delete p;

insert into p(n)
      WITH t AS (
         SELECT 2*ROWNUM+1 n FROM DUAL CONNECT BY ROWNUM <= (:n)/2-1-1
         )
      SELECT n
         FROM (SELECT n from t
               MINUS
               SELECT t1.n * t2.n
               FROM t t1, t t2
               WHERE t1.n <= t2.n
                     AND t1.n <= (SELECT SQRT(:n) FROM DUAL)
                     AND t1.n * t2.n <:n
            )
      union all select 2 from dual;

delete pairs;
insert into pairs(p1,p2)
      with pair as (
      select p1.n p1,p2.n p2
      from p p1,p p2
      where p1.n<p2.n
            and (substr(p2.n,2)=to_char(p1.n)
                  or (length(p1.n)=length(p2.n)
                     and to_number(rtrim(p2.n-p1.n,'0')) between 1 and 9
                     and substr(p2.n,-length(p2.n-p1.n),1)
                        >substr(p1.n,-length(p2.n-p1.n),1)
                     )
                  )
      )
      select p1,p2 from pair union all select p2,p1 from pair
      ;

delete res;

insert into res (wm,n,path)
select 0,p2,p2 from pairs where p1=2;

LOOP

   MERGE INTO res USING (

   select r2.*
      from (select pairs.p2 as n
                  ,MIN(CASE WHEN pairs.p1<pairs.p2 THEN CASE WHEN res.wm<pairs.p2 THEN 0 ELSE res.wm END
                           WHEN pairs.p1>pairs.p2 THEN greatest(res.wm, pairs.p1)
                     END) wm
                  ,min(res.path||','||pairs.p2) keep(dense_rank first order by
                     CASE WHEN pairs.p1<pairs.p2 THEN CASE WHEN res.wm<pairs.p2 THEN 0 ELSE res.wm END
                           WHEN pairs.p1>pairs.p2 THEN greatest(res.wm, pairs.p1)
                     END ) path
            from res join pairs on res.n=pairs.p1
            group by pairs.p2
         ) r2
         left join res res2 on r2.n=res2.n
   where res2.n is null
         or res2.n is NOT null
            AND r2.wm<res2.wm
   ) d
   ON (d.n=res.n)
   WHEN NOT MATCHED THEN INSERT (wm,n,path) values (d.wm,d.n,d.path)
   WHEN MATCHED THEN UPDATE SET wm=d.wm,path=d.path;

   EXIT WHEN SQL%ROWCOUNT=0;
END LOOP;

select sum(n) into f from res where wm>0 and n<>2;
dbms_output.put_line(f);
end;
/

78728

PL/SQL procedure successfully completed.

Elapsed: 00:00:01.00