Euler Project 挨个做- 之二 (Q51-Q78)

tree_new_bee

Q60 Find a set of five primes for which any two primes concatenate to produce another prime.

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

tree_new_bee

越来越难了。
Q60思路并不难， 难的是算法的效率。

在寻找题目中的4个数时，还算比较轻松。 到5个数时， 复杂度不是一般的大。

以下SQL可以解决4个数：

with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(900)))
,tpath as (select /*+ MATERIALIZE */ sys_connect_by_path(p,'/')||'/' path from t
       where level=4 connect by p > prior p and level<=4
       and pkg_prim2.isprim(p||prior p)=0 and pkg_prim2.isprim(prior p||p)=0 )
--select count(*) from tpath
,tall as (select * from tpath, t where instr(path, '/'||p||'/')>0)
--select a.path, a.p, b.p, pkg_prim2.isprim(a.p||b.p), pkg_prim2.isprim(b.p||a.p) from tall a, tall b where a.path=b.path  and a.p<b.p
select * from tpath c
where not exists (select 1 from tall a, tall b where a.path=c.path  and b.path=c.path and a.path=b.path
and a.p<b.p
and (pkg_prim2.isprim(a.p||b.p)>0 or pkg_prim2.isprim(b.p||a.p)>0))

PATH
--------------------------------------------------------------------------------
/3/7/109/673/
/23/311/677/827/

Executed in 20.781 seconds

改成5位(两处level的地方将4改成5)， 对1000以内的数进行计算已经让人无法接受了。
太慢, 每增加100，差不多要多一倍的时间
500:4s   600: 6.9s,  700:12s   ,800: 19s， 1000: 49.5s

而1000距离有解， 还早的很。

[ 本帖最后由 tree_new_bee 于 2011-1-3 00:44 编辑 ]

tree_new_bee

下面的plsql代码， 运行270秒， 可以找到一组解(似乎是344xx)， 但并不是最优解。
(结果那个界面关掉了， 我实在不想再重复执行一次，所以时间和结果都是凭记忆写下的)

create or replace procedure Q60B is
  i integer;
  pl t_numlist:=t_numlist();
  pit pkg_prim2.tprimtable;
  a integer := 1;
  b integer:= 1;
  c integer:= 1;
  d integer:= 1;
  e integer:= 1;
  function isprim(x number) return boolean is
  begin
    if x<10000000 then
      return pit.exists(x);
    else
      return (pkg_prim2.isprim(x)=0);
    end if;
  end;
begin
  pl := pkg_prim2.seive_numlist_nk(30000);
  pit := pkg_prim2.seive_indextable_nk(10000000);
  a:= 2;
  while a<pl.count loop
    b:=a+1;
    while b<pl.count loop
      if isprim(pl(a)||pl(b)) and isprim(pl(b)||pl(a)) then
         c:=b+1;
         while c<pl.count loop
           if isprim(pl(a)||pl(c)) and isprim(pl(c)||pl(a))
              and isprim(pl(b)||pl(c)) and isprim(pl(c)||pl(b))
           then
              d:=c+1;
              while d<pl.count loop
                 if isprim(pl(a)||pl(d)) and isprim(pl(d)||pl(a))
                    and isprim(pl(b)||pl(d)) and isprim(pl(d)||pl(b))
                    and isprim(pl(c)||pl(d)) and isprim(pl(d)||pl(c))
                 then
                   e:= d+1;
                    while e<pl.count loop
                       if isprim(pl(a)||pl(e)) and isprim(pl(e)||pl(a))
                          and isprim(pl(b)||pl(e)) and isprim(pl(e)||pl(b))
                          and isprim(pl(c)||pl(e)) and isprim(pl(e)||pl(c))
                          and isprim(pl(d)||pl(e)) and isprim(pl(e)||pl(d))
                       then
                         dbms_output.put_line('abcd:'||pl(a) ||','||pl(b)||','||pl(c)||','||pl(d)||','||pl(e));     
                         dbms_output.put_line('sum is:'||(pl(a)+pl(b)+pl(c)+pl(d)+pl(e)));     
                         return;   
                       end if;
                       e:=e+1;
                    end loop;
                 end if;
                 d:=d+1;
               end loop;
           end if;
           c:=c+1;
         end loop;        
      end if;
      b:=b+1;
    end loop;     
    a:=a+1;
  end loop;   
end;

这个算法，要得到最优解， 接下来要循环的次数是个天量数字。 所以必须另做考虑。

tree_new_bee

楼上的代码，问题出在bcde都是从小往大循环， 是个开口循环，所以可能会先得到非优解。
应该改成后面的变量从上个变量往小循环。
这样循环终止时， "abcde中最大的那个数" 是最小的， 这是最优解的可能性比较大(尽管似乎也并不一定完全保证)
明天再改。

tree_new_bee

下面是昨天的代码改写后的结果：
create or replace procedure Q60D is
  pit pkg_prim2.tprimtable;
  a integer := 1;
  b integer:= 1;
  c integer:= 1;
  d integer:= 1;
  e integer:= 1;
  function isprim(x number) return boolean is
  begin
    if x<10000000 then
      return pit.exists(x);
    else
      return (pkg_prim2.isprim(x)=0);
    end if;
  end;
begin
  pit := pkg_prim2.seive_indextable_nk(10000000);
  pit.delete(2);  pit.delete(5);
  a:= 13;
  while a<pit.last loop
    b:=11;
    while b<a loop
      if isprim(a||b) and isprim(b||a) then
         c:=7;
         while c<b loop
           if isprim(a||c) and isprim(c||a)
              and isprim(b||c) and isprim(c||b)
           then
              d:=3;
              while d<c loop
                 if isprim(a||d) and isprim(d||a)
                    and isprim(b||d) and isprim(d||b)
                    and isprim(c||d) and isprim(d||c)
                 then
                   e:= 3;
                    while e<d loop
                       if isprim(a||e) and isprim(e||a)
                          and isprim(b||e) and isprim(e||b)
                          and isprim(c||e) and isprim(e||c)
                          and isprim(d||e) and isprim(e||d)
                       then
                         dbms_output.put_line('abcde:'||a ||','||b||','||c||','||d||','||e);     
                         dbms_output.put_line('sum is:'||(a+b+c+d+e));     
                         return;   
                       end if;
                       e:=pit.next(e);
                    end loop;
                 end if;
                 d:=pit.next(d);
               end loop;
           end if;
           c:=pit.next(c);
         end loop;        
      end if;
      b:=pit.next(b);
    end loop;     
    a:=pit.next(a);
  end loop;   
end;

SQL> exec q60d

abcde:8389,6733,5701,5197,13
sum is:26033

PL/SQL procedure successfully completed

Executed in 1258.062 seconds


跑了20多分钟！ 不过，可喜的是这个似乎是最优解。

问题出在:a每次循环到一个大数时， bcde都要重复之前的计算，  要想法利用以前的成果才行。

zhangweicai74

看得头晕~
厉害

tree_new_bee

下面做些人肉分析，以避免做很多无用功。

我们看看1000以内符合条件的三个数，前两个数是3,7的有：
        3        7        109
        3        7        229
        3        7        541
        3        7        673
        3        7        823

既然第4个数与前三个数并到一起都必须是质数， 因为其它数都与3或者7冲突， 所以第4个数必然要在上面列表的第三个数中选取， 因此不必再去到所有质数中去寻找。
这样， 对于 (3,7,109), 我们只要在229/541/673/823中逐个测试即可。


用这种方法，写出下面的SQL:

with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(10000)) where column_value not in (2,5))
, t2 as (select t1.p p1, t2.p p2  from t t1, t t2
  where t2.p>t1.p
  and pkg_prim2.isprim(t1.p||t2.p)=0 and pkg_prim2.isprim(t2.p||t1.p)=0)
, t3 as (select t2.p1 p1, t2.p2 p2, t3.p2 p3  from t2, t2 t3
  where t3.p1=t2.p1
  and t3.p2>t2.p2
  and pkg_prim2.isprim(t2.p2||t3.p2)=0 and pkg_prim2.isprim(t3.p2||t2.p2)=0)
, t4 as (select t3.p1 p1, t3.p2 p2, t3.p3, t4.p3 p4  from t3, t3 t4
  where t4.p1=t3.p1  and t4.p2 = t3.p2
  and t4.p3>t3.p3
  and pkg_prim2.isprim(t3.p3||t4.p3)=0 and pkg_prim2.isprim(t4.p3||t3.p3)=0)
, t5 as (select t4.p1 p1, t4.p2 p2, t4.p3, t4.p4 p4, t5.p4 p5  from t4, t4 t5
  where t5.p1=t4.p1  and t5.p2 = t4.p2 and t5.p3=t4.p3
  and t5.p4>t4.p4
  and pkg_prim2.isprim(t4.p4||t5.p4)=0 and pkg_prim2.isprim(t5.p4||t4.p4)=0)
select p1,p2,p3,p4,p5, p1+p2+p3+p4+p5 total from t5


        P1         P2         P3         P4         P5      TOTAL
---------- ---------- ---------- ---------- ---------- ----------
        13       5197       5701       6733       8389      26033

Executed in 345.438 seconds

一点都不花哨， 从t3开始，后面的几乎就是前面简单的重复。
尽管仍然要近7分钟， 但比起之前的代码性能好多了。

〇〇

看scala的代码，把质数表做到1亿的，结果index by不支持
SQL> select count(*) from table(seive_numlist(10000000));

  COUNT(*)
----------
    664579

已用时间:  00: 00: 05.99
SQL> select count(*) from table(seive_numlist(100000000));
select count(*) from table(seive_numlist(100000000))
                           *
第 1 行出现错误:
ORA-22813: 操作数值超出系统的限制


已用时间:  00: 01: 02.60

tree_new_bee

原帖由 〇〇 于 2011-1-3 12:47 发表
看scala的代码，把质数表做到1亿的，结果index by不支持

我选1000万， 倒不是因为有限制。

而是因为，产生更大的质数表，开销太大。
但实际上10000以内的两个数，需要判断并起来判断是否质数的机会并不是特别多。 所以产生大质数表可能不如把这些操作改成低效判断方法更有效。
当然，这中间需要权衡。 如何选取最合适的数，也是个问题。

tree_new_bee

77#的sql， 如果把所有的>改成<，即从大往小排，则时间是310秒， 快了30多秒。
似乎是因为从大到小排的话，最后一个数的选择稍微少一些。
另外，循环到最后都是小数字， 小数与小数的并， 以及这个并起来的数判断是否质数， 效率都要好一些。