Euler Project 挨个做 - 之一(Q1-50)

tree_new_bee

实际上， 因为质数的密度还是很大的， 所以我们猜测那个大数的时候可以把区间放的再窄一些， 比如说猜测开头为7.
不过， 用上面的方法， 因为时间主要耗费在seive_numlist函数上， 所以缩小范围带来的收益并不大。

select max(column_value) from table(pkg_prim2.seive_numlist(7654321)) where column_value >=7123456
and translate('1234567' , '$'||column_value, '$') is null

MAX(COLUMN_VALUE)
-----------------
          7652413

Executed in 12.985 seconds


这时， 反过来先找全排列数再判断是否是质数，就能受益于范围的缩小了。

with t as (select level+7123455 n, translate('1234567' , '$'||(level+7123455), '$') from dual
where translate('1234567' , '$'||(level+7123455), '$') is null
and pkg_prim2.isprim(level+7123455)= 0
connect by level<=7654321-7123455)
select max(n) from t

    MAX(N)
----------
   7652413

Executed in 1.938 seconds


如果范围收的更窄一些， 还能更快：
with t as (select level+7612344 n, translate('1234567' , '$'||(level+7612344), '$') from dual
where translate('1234567' , '$'||(level+7612344), '$') is null
and pkg_prim2.isprim(level+7612344)= 0
connect by level<=7654321-7612344)
select max(n) from t

    MAX(N)
----------
   7652413

Executed in 0.235 seconds

起点如果改成7651234的话，就只要0.062秒了。

当然也可以考虑试试7654123, 这样试的结果是没有满足条件的数。

with t as (select level+7654122 n, translate('1234567' , '$'||(level+7654122), '$') from dual
where translate('1234567' , '$'||(level+7654122), '$') is null
and pkg_prim2.isprim(level+7654122)= 0
connect by level<=7654321-7654122)
select max(n) from t

    MAX(N)
----------

Executed in 0.031 seconds

[ 本帖最后由 tree_new_bee 于 2010-12-26 15:18 编辑 ]

〇〇

如果没有算错，7开头的7位数全排列只有6!=720种，所有的也只有7!=5040种
而末位只能选1 3 5 7。。。
判断质数只要sqrt(7700000）以内的质数表

〇〇

按212楼思路做的，不知错在哪里
var n number;
exec :n:=7700000
with t as (select level l from dual connect by level<=7)
,tb as
(
select to_number(t1.l||t2.l||t3.l||t4.l||t5.l||t6.l||t7.l) s
from t t1,t t2,t t3,t t4,t t5,t t6,t t7
where t7.l in ('1','3','5','7')
and t1.l not in(     t2.l,t3.l,t4.l,t5.l,t6.l,t7.l)
and t2.l not in(t1.l,     t3.l,t4.l,t5.l,t6.l,t7.l)
and t3.l not in(t1.l,t2.l,     t4.l,t5.l,t6.l,t7.l)
and t4.l not in(t1.l,t2.l,t3.l,     t5.l,t6.l,t7.l)
and t5.l not in(t1.l,t2.l,t3.l,t4.l,     t6.l,t7.l)
and t6.l not in(t1.l,t2.l,t3.l,t4.l,t5.l,     t7.l)
and t7.l not in(t1.l,t2.l,t3.l,t4.l,t5.l,t6.l     )
)
--select count(*) from tb --0.1s
,ta as
(select level*2+1 l from dual connect by level<=sqrt(:N)/2),
t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)
,p1k as(select l rn from ta --1000以内的质数
minus
select /*+ USE_MERGE (t1 t2) */ t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))
and t1.l<=t2.l and t1.l*t2.l<=:N
)
--select count(*) from p1k --0.1s
select max(s) from tb
where not exists(select 1 from p1k where mod(s,rn)=0 and rn<=sqrt(s));

〇〇

糟糕的执行时间，
    MAX(S)
----------
   7652413

已用时间:  00: 03: 58.51

tree_new_bee

原帖由 〇〇 于 2010-12-26 18:51 发表
糟糕的执行时间，

我的经验： 用产生质数列表，然后判断是否在列表中的方法来判断一些数是否是质数， 性能总是不如直接去每个分别判断是否是质数。

〇〇

怪哉，拆开分为3个sql,非常快

SQL> var n number; SQL> exec :n:=7700000 PL/SQL 过程已成功完成。 已用时间:  00: 00: 00.01 SQL> var n number; SQL> exec :n:=7700000 PL/SQL 过程已成功完成。 已用时间:  00: 00: 00.00 SQL> create table t_b as   2  with t as (select level l from dual connect by level<=7)   3  ,tb as   4  (   5  select to_number(t1.l||t2.l||t3.l||t4.l||t5.l||t6.l||t7.l) s   6  from t t1,t t2,t t3,t t4,t t5,t t6,t t7   7  where t7.l in ('1','3','5','7')   8  and t1.l not in(     t2.l,t3.l,t4.l,t5.l,t6.l,t7.l)   9  and t2.l not in(t1.l,     t3.l,t4.l,t5.l,t6.l,t7.l) 10  and t3.l not in(t1.l,t2.l,     t4.l,t5.l,t6.l,t7.l) 11  and t4.l not in(t1.l,t2.l,t3.l,     t5.l,t6.l,t7.l) 12  and t5.l not in(t1.l,t2.l,t3.l,t4.l,     t6.l,t7.l) 13  and t6.l not in(t1.l,t2.l,t3.l,t4.l,t5.l,     t7.l) 14  and t7.l not in(t1.l,t2.l,t3.l,t4.l,t5.l,t6.l     ) 15  ) 16  select * from tb; 表已创建。 已用时间:  00: 00: 00.16 SQL> create table p_1k(rn number(8,0)); 表已创建。 已用时间:  00: 00: 00.01 SQL> insert into p_1k   2  with ta as   3  (select level*2+1 l from dual connect by level<=sqrt(:N)/2),   4  t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)   5  ,p1k as(select l rn from ta --1000以内的质数   6  minus   7  select /*+ USE_MERGE (t1 t2) */ t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))   8  and t1.l<=t2.l and t1.l*t2.l<=:N   9  ) 10  select * from p1k; 已创建402行。 已用时间:  00: 00: 00.08 SQL> select max(s) from t_b   2  where not exists(select 1 from p_1k where mod(s,rn)=0 and rn<=sqrt(s) and s is not null);     MAX(S) ----------    7652413 已用时间:  00: 00: 00.20 SQL> explain plan for select max(s) from t_b   2  where not exists(select 1 from p_1k where mod(s,rn)=0 and rn<=sqrt(s) and s is not null); 已解释。 已用时间:  00: 00: 00.00 SQL> select * from table(dbms_xplan.display); PLAN_TABLE_OUTPUT -------------------------------------------------------------------------------------------------------------------------------------------- Plan hash value: 3757790328 ----------------------------------------------------------------------------- | Id  | Operation            | Name | Rows  | Bytes | Cost (%CPU)| Time     | ----------------------------------------------------------------------------- |   0 | SELECT STATEMENT     |      |     1 |    13 |   275   (1)| 00:00:04 | |   1 |  SORT AGGREGATE      |      |     1 |    13 |            |          | |*  2 |   FILTER             |      |       |       |            |          | |   3 |    TABLE ACCESS FULL | T_B  |  2880 | 37440 |     4   (0)| 00:00:01 | |*  4 |    FILTER            |      |       |       |            |          | |*  5 |     TABLE ACCESS FULL| P_1K |     1 |    13 |     3   (0)| 00:00:01 | ----------------------------------------------------------------------------- Predicate Information (identified by operation id): ---------------------------------------------------    2 - filter( NOT EXISTS (SELECT 0 FROM "P_1K" "P_1K" WHERE :B1 IS NOT               NULL AND MOD(:B2,"RN")=0 AND "RN"<=SQRT(:B3)))    4 - filter(:B1 IS NOT NULL)    5 - filter(MOD(:B1,"RN")=0 AND "RN"<=SQRT(:B2)) Note -----    - dynamic sampling used for this statement (level=2) 已选择24行。 已用时间:  00: 00: 00.03 SQL>

tree_new_bee

原帖由 〇〇 于 2010-12-26 19:20 发表
怪哉，拆开分为3个sql,非常快

对于这些通过dual表产生的大量数据， oracle优化器在执行之前很难得到有用的信息帮助优化。

〇〇

捣鼓半天，消除了谓词推进的查询重写
with t as (select level l from dual connect by level<=7)
,tb as
(
select /*+ MATERIALIZE */t1.l||t2.l||t3.l||t4.l||t5.l||t6.l||t7.l s
from t t1,t t2,t t3,t t4,t t5,t t6,t t7
where t7.l in ('1','3','5','7')
and t1.l not in(     t2.l,t3.l,t4.l,t5.l,t6.l,t7.l)
and t2.l not in(t1.l,     t3.l,t4.l,t5.l,t6.l,t7.l)
and t3.l not in(t1.l,t2.l,     t4.l,t5.l,t6.l,t7.l)
and t4.l not in(t1.l,t2.l,t3.l,     t5.l,t6.l,t7.l)
and t5.l not in(t1.l,t2.l,t3.l,t4.l,     t6.l,t7.l)
and t6.l not in(t1.l,t2.l,t3.l,t4.l,t5.l,     t7.l)
and t7.l not in(t1.l,t2.l,t3.l,t4.l,t5.l,t6.l     )
)
--select count(*) from tb
,ta as
(select level*2+1 l from dual connect by level<=sqrt(:N)/2),
t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)
,p1k as(select /*+ MATERIALIZE */ * from (select l rn from ta --1000以内的质数
minus
select /*+ USE_MERGE (t1 t2) */ t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))
and t1.l<=t2.l and t1.l*t2.l<=:N
))
--select count(*) from p1k
select max(s) from tb --(select rownum rn2,s from tb)tb
where not exists(select 1 from /*(select rownum rn1,rn from p1k)*/p1k where mod(s,rn)=0);

S)
------------------------------------------------------------------------------------------
413

时间:  00: 00: 00.07（实际是0.7秒）

newkid

可以试一下CONNECT BY做全排列：
with t as (select level l from dual connect by level<=7)
,tb AS
(
SELECT REPLACE(SYS_CONNECT_BY_PATH(l,','),',') s
  FROM t
WHERE LEVEL=7
CONNECT BY NOCYCLE l<>PRIOR l AND LEVEL<=7
)
--select count(*) from tb
,ta as
(select level*2+1 l from dual connect by level<=sqrt(:N)/2),
t1 as (select level*2+1 l from dual connect by level<=sqrt(:N)/3)
,p1k as(select /*+ MATERIALIZE */ * from (select l rn from ta --1000以内的质数
minus
select /*+ USE_MERGE (t1 t2) */ t1.l*t2.l from t1,t1 t2 where t1.l<=sqrt(sqrt(:N))
and t1.l<=t2.l and t1.l*t2.l<=:N
))
--select count(*) from p1k
select max(s) from tb --(select rownum rn2,s from tb)tb
where not exists(select 1 from /*(select rownum rn1,rn from p1k)*/p1k where mod(s,rn)=0);

〇〇

由于我的质数表不包括2,需要修改
with t as (select level l from dual connect by level<=7)
,tb AS
(
SELECT reverse(REPLACE(SYS_CONNECT_BY_PATH(l,','),',')) s
  FROM t
WHERE LEVEL=7
start with l in('1','3','7')
CONNECT BY NOCYCLE l<>PRIOR l AND LEVEL<=7
)