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

〇〇 · 发表于 2011-1-4 11:32

86楼改用pkg_prim2.isprimj
已用时间: 00: 01: 22.63

〇〇 · 发表于 2011-1-4 16:10

终于把89楼改对了，性能测试
loadjava -u rk/rk -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> select count(l) from(select level l, pkg_prim2.isprimj(level)i from dual connect by level<=1000000)where i=0;

COUNT(L)
--------
78499

已用时间:  00: 00: 49.82
SQL>
SQL> select count(l) from(select level l, pkg_prim2.isprim(level)i from dual connect by level<=1000000)where i=0;

COUNT(L)
--------
78498

已用时间:  00: 00: 19.23
SQL> select rk.init(1000000)x from dual;

   X
--------
   1

已用时间:  00: 00: 00.24
SQL> select count(l) from(select level l, rk.isprimo(level)i from dual connect by level<=1000000)where i=1;

COUNT(L)
--------
78498

已用时间:  00: 00: 13.64

但
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 isprimo(t1.p||t2.p)=0 and isprimo(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;
20分钟了也不出结果

终于明白错在哪里了，原来我的函数用1表示质数，而tnb用0
SQL> select rk.init(100000000) from dual;

RK.INIT(100000000)
------------------
               1

已用时间:  00: 00: 28.11
SQL> @d:\app\oop.txt

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

已用时间:  00: 00: 13.01

SQL> @d:\app\oop1.txt
SQL> /

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

已用时间:  00: 00: 16.94
SQL> 3
  3* where t2.p>t1.p
SQL> c/>/<
  3* where t2.p<t1.p
SQL> /

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

已用时间:  00: 00: 17.45

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

〇〇 · 发表于 2011-1-4 16:41

工具包初始化性能测试
SQL> select rk.init(100000000) from dual;

RK.INIT(100000000)
------------------
               1

已用时间:  00: 00: 26.80
SQL> select rk.init(200000000) from dual;

RK.INIT(200000000)
------------------
               1

已用时间:  00: 00: 54.36
SQL> select rk.init(800000000) from dual;

RK.INIT(800000000)
------------------
               1

已用时间:  00: 03: 51.09

tree_new_bee · 发表于 2011-1-4 17:03

原帖由 newkid 于 2011-1-4 03:18 发表
装修77楼：因为T2已经算出了所有满足条件的质数对，从T3开始没有必要再调用pkg_prim2.isprim, 就和T2做个连接就行。

Elapsed: 00:02:20.36

装修前：
Elapsed: 00:03:57.78

这个出乎我的预料之外。

这样的做法我想过，但我觉得T2的数据量太大，在内存表无索引的情况下，以为一定比再判断质数更差。所以没尝试就放弃了

〇〇 · 发表于 2011-1-4 19:27

9i的java测试貌似比10g,11g都快

SQL> set def off
SQL> create or replace and compile java source named oop as
  2  import java.io.PrintStream;
  3
  4  public class oop
  5  {
  6
  7
  8    public static int getisp(int j)
  9    {
10       if ((j & 1)==0)return (j==2)?1:0;
11       if (j<=1) return 0;
12       int i=(j - 1) / 2;
13       return isprime[i >> 3] >> (i & 7) & 1;
14    }
15
16    public static int init(int i)
17    {
18
19       int j = (i + 1) / 2; //只保存奇数
20       isprime = new byte[j / 8 + 2]; //用一个bit保存一个奇数
21       int k = 0;
22       for(int l = 0; l <= j / 8 + 1; l++) //初始化为bit全1
23             isprime[l] = -1;
24
25       isprime[0] &= 0xfe;
26       isprime[0] |= 2; //把1的位设为0
27       int k1 = (int)Math.ceil(Math.sqrt(i));//根号max是被乘数的上限
28       int i1 = (i - 1) / 2;
29       for(int i2 = 4; i2 <= i1; i2 += 3)  //设置所有3的倍数
30             isprime[i2 >> 3] &= ~(1 << (i2 & 7));
31
32       char c = '\0';
33       int j2 = (k1 - 1) / 2; //根号max在 isprime的地址
34       int k2 = (i - 1) / 2; //max在 isprime的地址
35       for(int j1 = 2; j1 <= j2; j1++) //j1是被乘数，3 5 7 ...必须是质数
36       {
37             c++;
38             if(c == '\003')
39                c = '\0';
40             else
41             if((isprime[j1 >> 3] >> (j1 & 7) & 1) == 1)
42             {
43                int l1 = ((j1 << 2) + 1) % 3;
44                for(int l2 = j1 * (2 * j1 + 2); l2 <= k2; l2 = l2 + j1 + j1 + 1)//l2是
45                   if(++l1 == 3)//忽略所有3的倍数，不再重复设置
46                         l1 = 0;
47                   else
48                   if((isprime[l2 >> 3] >> (l2 & 7) & 1) == 1)
49                         isprime[l2 >> 3] &= ~(1 << (l2 & 7));//置为0
50
51             }
52       }
53       return 1;
54
55    }
56
57    static byte isprime[];
58  }
59  /

Java 已创建。

已用时间:  00: 00: 10.04
SQL> create or replace FUNCTION isprimo(x NUMBER) RETURN NUMBER AS LANGUAGE JAVA NAME 'oop.getisp

(int) return int';
  2  /

函数已创建。

已用时间:  00: 00: 00.03
SQL> create or replace FUNCTION init(x NUMBER) RETURN NUMBER AS LANGUAGE JAVA NAME 'oop.init(int)

return int';
  2  /

函数已创建。

已用时间:  00: 00: 00.00
SQL>
SQL> select init(1000000) from dual;

INIT(1000000)
-------------
         1

已用时间:  00: 00: 00.03
SQL> select count(l) from(select level l, isprimo(level)i from dual connect by level<=1000000)

where i=1
SQL> /

  COUNT(L)
----------
   78498

已用时间:  00: 00: 11.06
SQL> select init(10000000) from dual;

INIT(10000000)
--------------
         1

已用时间:  00: 00: 01.00
SQL> select init(100000000) from dual;

INIT(100000000)
---------------
            1

已用时间:  00: 00: 09.01
SQL>
SQL> select count(l) from(select level l, pkg_prim2.isprimj(level)i from dual connect by level<=1000000)where i=0;

  COUNT(L)
----------
   78499

已用时间:  00: 00: 34.04
SQL>
SQL> select count(l) from(select level l, pkg_prim2.isprim(level)i from dual connect by level<=1000000)where i=0;

  COUNT(L)
----------
   78498

已用时间:  00: 00: 44.06
SQL>
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 isprimo(t1.p||t2.p)=0 and isprimo(t2.p||t1.p)=0)
  5  , t3 as (select t2.p1, t2.p2, t3.p2 p3  from t2, t2 t3, t2 pairs
  6 where t3.p1=t2.p2
  7 and t2.p1=pairs.p1 and t3.p2=pairs.p2
  8 )
  9  , t4 as (select t3.p1, t3.p2, t3.p3, t4.p3 p4  from t3, t3 t4, t2 pairs
10 where t3.p2=t4.p1 AND t3.p3=t4.p2
11 and t3.p1=pairs.p1 and t4.p3=pairs.p2
12 )
13  , t5 as (select t4.p1, t4.p2, t4.p3, t4.p4, t5.p4 p5  from t4, t4 t5, t2 pairs
14 where t4.p2=t5.p1 AND t4.p3=t5.p2 AND t4.p4=t5.p3
15 and t4.p1=pairs.p1 and t5.p4=pairs.p2
16 )
17  select p1,p2,p3,p4,p5, p1+p2+p3+p4+p5 total from t5;
with t as (select /*+ MATERIALIZE */ column_value p from table(pkg_prim2.seive_numlist(10000)) where column_value not in (2,5))
                                                                  *
ERROR 位于第 1 行:
ORA-00604: 递归 SQL 层 1 出现错误
ORA-01652: 无法通过2048（在表空间LTTEMPTS中）扩展 temp 段

已用时间:  00: 00: 19.06
SQL> 4
  4* and isprimo(t1.p||t2.p)=0 and isprimo(t2.p||t1.p)=0)
SQL> c/0/1
  4* and isprimo(t1.p||t2.p)=1 and isprimo(t2.p||t1.p)=0)
SQL> c/0/1
  4* and isprimo(t1.p||t2.p)=1 and isprimo(t2.p||t1.p)=1)
SQL> /

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

已用时间:  00: 00: 10.01
SQL>
D:\lt\dl>D:\Oracle\ora92\jdk\bin\javac -classpath . Sieve5.java

D:\lt\dl>D:\Oracle\ora92\jdk\bin\java -classpath . Sieve5
The largest prime less than or equal to 100000000 is 99999989 cycle time:0
cost 906ms

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

tree_new_bee · 发表于 2011-1-5 12:24

Q62 Find the smallest cube for which exactly five permutations of its digits are cube.

The cube, 41063625 (345^(3)), can be permuted to produce two other cubes: 56623104 (384^(3)) and 66430125 (405^(3)). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

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

tree_new_bee · 发表于 2011-1-5 12:42

这个简单，只要把立方数的各位数字排个序，就很容易找到。

with t as (select level n, level*level*level cb from dual connect by level <=10000)
,td as (select n, cb, substr(cb,d,1) digi, row_number() over(partition by cb order by substr(cb,d,1)) rn
from t, (select rownum d from dual connect by rownum<=length(power(10000,3)))
where d<=length(cb))
,tdigis as (select  n, cb, replace(sys_connect_by_path(digi,'/'),'/','') digis from td
where level = length(cb)
connect by  n=prior n and rn=prior rn+1
)
select min(n),to_char(min(cb)) cb  from tdigis where digis in (select digis from tdigis group by digis having count(*)=5)

MIN(N) CB
---------- ----------------------------------------
   5027 127035954683

Executed in 6.828 seconds

数字排序做的很绕，但没想出简明的办法。

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

tree_new_bee · 发表于 2011-1-5 13:36

Q63 How many n-digit positive integers exist which are also an nth power?

The 5-digit number, 16807=7^(5), is also a fifth power. Similarly, the 9-digit number, 134217728=8^(9), is a ninth power.

How many n-digit positive integers exist which are also an nth power?

这个题，纯粹是个数学题了。
基本上就是人肉+程序辅助。

要满足要求，底不能大于等于10 ，因为10的任意次幂都比相应的幂多一位。

幂次用程序循环一下，就能发现： 9^21是1.09*10^20，再往后位数就不够了。

with tn as (select rownum n from dual connect by rownum<=9)
,tp as (select rownum p from dual connect by rownum<=100)
select count(*) from tn, tp
where length(power(n,p)) = p

COUNT(*)
----------
49

Executed in 0.032 seconds

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

tree_new_bee · 发表于 2011-1-5 13:59

Q64 How many continued fractions for N ≤ 10000 have an odd period?

64题抄也抄不过来，描述也描述不清楚。
直接去看原题吧：
http://projecteuler.net/index.php?section=problems&id=64

这个题做出来，基本就能自己实现大数开方了。

tree_new_bee · 发表于 2011-1-5 14:30

先写段代码，模拟题目的操作：
with t(r, n1, n2) as
(select 1, 23,sqrt(23)  from dual
union all
select
r+1,
floor(n2),
1/(n2 - floor(n2))
from t  where r<=100 and n2 - floor(n2)>0 )
select * from t

前面看好像问题：
      R       N1       N2
---------- ---------- ----------
      1       23 4.79583152
      2       4 1.25654736
      3       1 3.89791576
      4       3 1.11369021
      5       1 8.79583152
      6       8 1.25654736
      7       1 3.89791576
      8       3 1.11369021
      9       1 8.79583152
      10       8 1.25654736

但到了后面，就有精度问题了：
....
      43       1 3.89843897
      44       3 1.11304165
      45       1 8.84629643
      46       8 1.18161906
      47       1 5.50602986
      48       5 1.97616793
      49       1 1.02441390
      50       1 40.9602673

由于精度问题，到后面就不正确了。
所以这个方法行不通，要绕开sqrt运算，直接用整数运算才行。