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

〇〇

原帖由 tree_new_bee 于 2011-1-3 13:09 发表


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

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

大部分时间花在第二步:

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

已用时间:  00: 03: 53.47
SQL> with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(10000)) where column_value not in (2,5))
  2  , t2 as (select t1.p p1, t2.p p2  from t t1, t t2
  3    where t2.p>t1.p
  4    and pkg_prim2.isprim(t1.p||t2.p)=0 and pkg_prim2.isprim(t2.p||t1.p)=0)
  5  , t3 as (select t2.p1 p1, t2.p2 p2, t3.p2 p3  from t2, t2 t3
  6    where t3.p1=t2.p1
  7    and t3.p2>t2.p2
  8    and pkg_prim2.isprim(t2.p2||t3.p2)=0 and pkg_prim2.isprim(t3.p2||t2.p2)=0)
  9  select count(*) from t3;

  COUNT(*)
----------
      9904

已用时间:  00: 03: 51.52

SQL>  with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(10000)) where column_value not in (2,5))
  2   , t2 as (select t1.p p1, t2.p p2  from t t1, t t2
  3     where t2.p>t1.p
  4     and pkg_prim2.isprim(t1.p||t2.p)=0 and pkg_prim2.isprim(t2.p||t1.p)=0)
  5  select count(*)from t2;

  COUNT(*)
----------
     18176

已用时间:  00: 02: 17.06
SQL> with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(10000)) where column_value not in (2,5))
  2  , t2 as (select t1.p p1, t2.p p2  from t t1, t t2
  3    where t2.p>t1.p)
  4  select count(*)from t2;

  COUNT(*)
----------
    752151

已用时间:  00: 00: 00.14
SQL> with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(10000)) where column_value not in (2,5))
  2  , t2 as (select t1.p p1, t2.p p2  from t t1, t t2
  3    where t2.p>t1.p)
  4  select length(p1||p2),count(*)cnt from t2 group by   length(p1||p2) order by 2;

LENGTH(P1||P2)        CNT
-------------- ----------
             2          1
             3         42
             4        496
             5       5125
             6      32434
             7     151723
             8     562330

已选择7行。

已用时间:  00: 00: 01.06
SQL> with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(10000)) where column_value not in (2,5))
  2  , t2 as (select t1.p p1, t2.p p2  from t t1, t t2
  3    where t2.p>t1.p)
  4  select substr(p1||p2,1,1),count(*)cnt from t2 where length(p1||p2)=8 group by substr(p1||p2,1,1)  order by 2;

SU        CNT
-- ----------
9        6216
8       18315
7       29425
6       45279
5       57285
4       73661
3       88620
2      109474
1      134055

已选择9行。

已用时间:  00: 00: 01.59

如果能把质数表做在3000万,用exist判断（2分查找？）应该能减少很多mod

tree_new_bee

原帖由 〇〇 于 2011-1-3 13:25 发表

大部分时间花在第二步:

没错， 在2个数和三个数的情况下， 组合非常多，并且可排除的组合不多。 到第4个数后就好多了， 组合数会锐减。

如果能把质数表做在3000万,用exist判断（2分查找？）应该能减少很多mod

下面用一个5000万以内的IOT表来尝试：
CREATE TABLE prim50M
( p number primary key)
ORGANIZATION INDEX ;

insert into prim50M select column_value p from table(pkg_prim2.seive_numlist_nk(50000000));

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 ((t1.p||t2.p <= 50000000 and exists(select 1 from prim50M where p=t1.p||t2.p))
      or (t1.p||t2.p >50000000 and (pkg_prim2.isprim(t1.p||t2.p)=0)))
  and ((t2.p||t1.p <=50000000 and exists(select 1 from prim50M where p=t2.p||t1.p))
      or (t2.p||t1.p >50000000 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 ((t2.p2||t3.p2 <= 50000000 and exists(select 1 from prim50M where p=t2.p2||t3.p2))
      or (t2.p2||t3.p2 >50000000 and (pkg_prim2.isprim(t2.p2||t3.p2)=0)))
  and ((t3.p2||t2.p2 <=50000000 and exists(select 1 from prim50M where p=t3.p2||t2.p2))
      or (t3.p2||t2.p2 >50000000 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 ((t3.p3||t4.p3 <= 50000000 and exists(select 1 from prim50M where p=t3.p3||t4.p3))
      or (t3.p3||t4.p3 >50000000 and (pkg_prim2.isprim(t3.p3||t4.p3)=0)))
  and ((t4.p3||t3.p3 <=50000000 and exists(select 1 from prim50M where p=t4.p3||t3.p3))
      or (t4.p3||t3.p3 >50000000 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 ((t4.p4||t5.p4 <= 50000000 and exists(select 1 from prim50M where p=t4.p4||t5.p4))
      or (t4.p4||t5.p4 >50000000 and (pkg_prim2.isprim(t4.p4||t5.p4)=0)))
  and ((t5.p4||t4.p4 <=50000000 and exists(select 1 from prim50M where p=t5.p4||t4.p4))
      or (t5.p4||t4.p4 >50000000 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
---------- ---------- ---------- ---------- ---------- ----------
      8389       6733       5701       5197         13      26033

Executed in 215.281 seconds


应该说效果还是很明显的。  不过要是加上为了生成prim50M而花费的时间， 那就不怎么划算了。

tree_new_bee

Q61 Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
Triangle                   P_(3,n)=n(n+1)/2                   1, 3, 6, 10, 15, ...
Square                   P_(4,n)=n^(2)                   1, 4, 9, 16, 25, ...
Pentagonal                   P_(5,n)=n(3n−1)/2                   1, 5, 12, 22, 35, ...
Hexagonal                   P_(6,n)=n(2n−1)                   1, 6, 15, 28, 45, ...
Heptagonal                   P_(7,n)=n(5n−3)/2                   1, 7, 18, 34, 55, ...
Octagonal                   P_(8,n)=n(3n−2)                   1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

   1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
   2. Each polygonal type: triangle (P_(3,127)=8128), square (P_(4,91)=8281), and pentagonal (P_(5,44)=2882), is represented by a different number in the set.
   3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

大意:
找出6个数， 分别是三角数、平方数、五边形数、六边形数、七边形数、八边形数
其中某个数的后两个数字，是另一个数的头两位数字， 形成一个环形的链

举例：8128, 8281, 2882 这3个数分别是三角数、平方数、五边形数，
而8128 -> 2882 -> 8281 ->8128 则形成一个链

[ 本帖最后由 tree_new_bee 于 2011-1-5 12:25 编辑 ]

tree_new_bee

这道比较简单。

with t as (select 3 id, level*(level-1)/2 n from dual where level*(level-1)/2>=1000 connect by level*(level-1)/2 <=9999
union all select 4 id, level*level n from dual where level*level>=1000 connect by level*level <=9999
union all select 5 id, level*(3*level-1)/2 n from dual where level*(3*level-1)/2>=1000 connect by level*(3*level-1)/2 <=9999
union all select 6 id, level*(2*level-1) n from dual where level*(2*level-1)>=1000 connect by level*(2*level-1) <=9999
union all select 7 id, level*(5*level-3)/2 n from dual where level*(5*level-3)/2>=1000 connect by level*(5*level-3)/2 <=9999
union all select 8 id, level*(3*level-2) n from dual where level*(3*level-2)>=1000 connect by level*(3*level-2) <=9999)
select t1.n+t2.n+t3.n+t4.n+t5.n+t6.n "SUM",t1.n,t2.n,t3.n,t4.n,t5.n,t6.n, t1.id||t2.id||t3.id||t4.id||t5.id||t6.id ids
from t t1, t t2, t t3 ,t t4, t t5, t t6
where t1.n < t2.n and t1.n<t3.n and t1.n<t4.n and t1.n<t5.n and t1.n<t6.n
and substr(t1.n,3) = substr(t2.n, 1,2)
and substr(t2.n,3) = substr(t3.n, 1,2)
and substr(t3.n,3) = substr(t4.n, 1,2)
and substr(t4.n,3) = substr(t5.n, 1,2)
and substr(t5.n,3) = substr(t6.n, 1,2)
and substr(t6.n,3) = substr(t1.n, 1,2)
and translate('345678', t1.id||t2.id||t3.id||t4.id||t5.id||t6.id||'345678', t1.id||t2.id||t3.id||t4.id||t5.id||t6.id ) = '345678'


       SUM          N          N          N          N          N          N IDS
---------- ---------- ---------- ---------- ---------- ---------- ---------- --------------------------------------------------------------------------------
     28684       1281       8128       2882       8256       5625       2512 865347

Executed in 1.219 seconds

newkid

#77逐步筛选的写法非常好！

newkid

装修77楼：因为T2已经算出了所有满足条件的质数对，从T3开始没有必要再调用pkg_prim2.isprim, 就和T2做个连接就行。
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, t2.p2, t3.p2 p3  from t2, t2 t3, t2 pairs
  where t3.p1=t2.p2
  and t2.p1=pairs.p1 and t3.p2=pairs.p2
  )
, t4 as (select t3.p1, t3.p2, t3.p3, t4.p3 p4  from t3, t3 t4, t2 pairs
  where t3.p2=t4.p1 AND t3.p3=t4.p2
  and t3.p1=pairs.p1 and t4.p3=pairs.p2
  )
, t5 as (select t4.p1, t4.p2, t4.p3, t4.p4, t5.p4 p5  from t4, t4 t5, t2 pairs
  where t4.p2=t5.p1 AND t4.p3=t5.p2 AND t4.p4=t5.p3
  and t4.p1=pairs.p1 and t5.p4=pairs.p2
  )
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

Elapsed: 00:02:20.36

装修前：
Elapsed: 00:03:57.78

〇〇

t2用82楼
已用时间:  00: 01: 53.21，但是
SQL> CREATE TABLE prim50M
  2  ( p number);

表已创建。

已用时间:  00: 00: 00.00
SQL> insert into prim50M select column_value p from table(seive_numlist(50000000));

已创建3001134行。

已用时间:  00: 00: 25.33
SQL> create unique index p50 on prim50M(p) parallel 6;

索引已创建。

已用时间:  00: 00: 02.29
82#
已用时间:  00: 02: 37.62
86#
已用时间:  00: 02: 15.54
总时间还是86#划算

〇〇

怪哉我用80楼方法<代替>
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, t2.p2, t3.p2 p3  from t2, t2 t3, t2 pairs
   where t3.p1=t2.p2
   and t2.p1=pairs.p1 and t3.p2=pairs.p2
   )
, t4 as (select t3.p1, t3.p2, t3.p3, t4.p3 p4  from t3, t3 t4, t2 pairs
   where t3.p2=t4.p1 AND t3.p3=t4.p2
   and t3.p1=pairs.p1 and t4.p3=pairs.p2
   )
, t5 as (select t4.p1, t4.p2, t4.p3, t4.p4, t5.p4 p5  from t4, t4 t5, t2 pairs
   where t4.p2=t5.p1 AND t4.p3=t5.p2 AND t4.p4=t5.p3
   and t4.p1=pairs.p1 and t5.p4=pairs.p2
   )
select p1,p2,p3,p4,p5, p1+p2+p3+p4+p5 total from t5;
已用时间:  00: 02: 40.52

〇〇

我测试用java筛选质数很快，1亿大约1秒，但不知怎么把数据导入plsql表

大概试一下，可以用了，但筛法有错误，正在修改
loadjava -u LT/LT -v -resolve d:\app\oop3.java

create or replace FUNCTION isprimo(x NUMBER) RETURN NUMBER AS LANGUAGE JAVA NAME 'oop.getisp(int) return int';
/
create or replace FUNCTION init(x NUMBER) RETURN NUMBER AS LANGUAGE JAVA NAME 'oop.init(int) return int';
/

SQL> with t as(select init(100000000)x from dual)select l from(select level l, isprimo(level)i from t connect by level<=1E2)where i=1;

         L
----------
         1
         2
         3
         5
         7
        11
        13
        17
        19
        23
        25

怪哉，seive5.java能输出正确，但改成oop3就是不对。。。
另外，执行一次select init(100000000)x from dual要几十秒

[ 本帖最后由 〇〇 于 2011-1-4 15:14 编辑 ]

〇〇

project.net论坛上的纯java版
D:\app>"C:\Program Files\Java\jdk1.7.0\bin\java" -cp . Problem60
26033
cost 10594ms