Project Euler Problem 276, 268, 347

〇〇

这样下去是不行的
SQL> 18
18* ,k as (select level l from dual connect by level<=1000)
SQL> c/1000/1E4
18* ,k as (select level l from dual connect by level<=1E4)
SQL> /

  COUNT(L)
----------
       811

已选择 1 行。

已用时间:  00: 00: 00.81
SQL> 18
18* ,k as (select level l from dual connect by level<=1E4)
SQL> c/4/5   
18* ,k as (select level l from dual connect by level<=1E5)
SQL> /

  COUNT(L)
----------
      9280

已选择 1 行。

已用时间:  00: 00: 07.75
加了约束条件也没什么用
SQL> var m number
SQL> exec :m:=1000

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> WITH
  2  t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
  3      )
  4  ,p AS (
  5  SELECT pn,LOG(10,pn) lg
  6  FROM (
  7  SELECT 2 pn FROM DUAL
  8  UNION ALL
  9        SELECT rn pn from t
10        MINUS
11        SELECT t1.rn * t2.rn
12          FROM t t1, t t2
13        WHERE t1.rn <= t2.rn
14              AND t1.rn <=SQRT(:n)
15              AND t1.rn * t2.rn <:n/2
16        )
17  )
18  ,k as (select level l from dual connect by level<=:m)
19  select count(l) from k where exists(select 1 from p p1,p p2,p p3,p p4
20  where
21  p2.pn<:m/p1.pn and
22  p3.pn<:m/p1.pn/p2.pn and
23  p4.pn<:m/p1.pn/p2.pn/p3.pn and
24  mod(l,p1.pn) =0 and
25  mod(l,p2.pn) =0 and mod(l,p3.pn) =0 and mod(l,p4.pn) =0
26  and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn);

  COUNT(L)
----------
        23

已选择 1 行。

已用时间:  00: 00: 00.11
SQL> exec :m:=1e4

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> /

  COUNT(L)
----------
       811

已选择 1 行。

已用时间:  00: 00: 00.92
SQL> exec :m:=1e5

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> /

  COUNT(L)
----------
      9280

已选择 1 行。

已用时间:  00: 00: 08.88
SQL> WITH
  2  t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
  3      )
  4  ,p AS (
  5  SELECT pn,LOG(10,pn) lg
  6  FROM (
  7  SELECT 2 pn FROM DUAL
  8  UNION ALL
  9        SELECT rn pn from t
10        MINUS
11        SELECT t1.rn * t2.rn
12          FROM t t1, t t2
13        WHERE t1.rn <= t2.rn
14              AND t1.rn <=SQRT(:n)
15              AND t1.rn * t2.rn <:n/2
16        )order by pn
17  )
18  ,k as (select level l from dual connect by level<=:m)
19  select count(l) from k where exists(select 1 from p p1,p p2,p p3,p p4
20  where
21  p2.pn<:m/p1.pn and
22  p3.pn<:m/p1.pn/p2.pn and
23  p4.pn<:m/p1.pn/p2.pn/p3.pn and
24  mod(l,p1.pn) =0 and
25  mod(l,p2.pn) =0 and mod(l,p3.pn) =0 and mod(l,p4.pn) =0
26  and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn);

  COUNT(L)
----------
      9280

已选择 1 行。

已用时间:  00: 00: 08.85
SQL> create table p as WITH
  2  t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((:n)/2-1-1)/2)
  3      )SELECT pn,LOG(10,pn) lg
  4  FROM (
  5  SELECT 2 pn FROM DUAL
  6  UNION ALL
  7        SELECT rn pn from t
  8        MINUS
  9        SELECT t1.rn * t2.rn
10          FROM t t1, t t2
11        WHERE t1.rn <= t2.rn
12              AND t1.rn <=SQRT(:n)
13              AND t1.rn * t2.rn <:n/2
14        )order by pn;
        FROM t t1, t t2
             *
第 10 行出现错误:
ORA-01027: 在数据定义操作中不允许有绑定变量

加了索引也只提高了1倍
已用时间:  00: 00: 00.00
SQL> create table p as
  2  with
  3  t as(SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= CEIL(((200)/2-1-1)/2)
  4      )
  5  SELECT pn,LOG(10,pn) lg
  6  FROM (
  7  SELECT 2 pn FROM DUAL
  8  UNION ALL
  9        SELECT rn pn from t
10        MINUS
11        SELECT t1.rn * t2.rn
12          FROM t t1, t t2
13        WHERE t1.rn <= t2.rn
14              AND t1.rn <=SQRT(200)
15              AND t1.rn * t2.rn <200/2
16        )order by pn;

表已创建。

已用时间:  00: 00: 00.04
SQL> create index ppn on p(pn);

索引已创建。

已用时间:  00: 00: 00.02
SQL> with k as (select level l from dual connect by level<=:m)
  2  select count(l) from k where exists(select 1 from p p1,p p2,p p3,p p4
  3  where
  4  p2.pn<:m/p1.pn and
  5  p3.pn<:m/p1.pn/p2.pn and
  6  p4.pn<:m/p1.pn/p2.pn/p3.pn and
  7  mod(l,p1.pn) =0 and
  8  mod(l,p2.pn) =0 and mod(l,p3.pn) =0 and mod(l,p4.pn) =0
  9  and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn);

  COUNT(L)
----------
      9280

已选择 1 行。

已用时间:  00: 00: 04.25
SQL>

〇〇

exist还不如直接连接快一点
SQL> with k as (select level l from dual connect by level<=:m)
  2  select count(unique l) from k/* where exists(select 1 from*/, p p1,p p2,p p3,p p4
where
p2.pn<:m/p1.pn and
p3.pn<:m/p1.pn/p2.pn and
p4.pn<:m/p1.pn/p2.pn/p3.pn and
  3    4    5    6    7  mod(l,p1.pn) =0 and
  8  mod(l,p2.pn) =0 and mod(l,p3.pn) =0 and mod(l,p4.pn) =0
  9  and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn);
and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn)
                                               *
第 9 行出现错误:
ORA-00933: SQL 命令未正确结束


已用时间:  00: 00: 00.01
SQL> 9
  9* and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn)
SQL> c/)/
  9* and p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn
SQL> /

COUNT(UNIQUEL)
--------------
          9280

已选择 1 行。

已用时间:  00: 00: 02.21

〇〇

用野花先算出质数积的点子更慢
SQL> create table p2 as
  2  select p1.pn*p2.pn*p3.pn*p4.pn mp
  3  from p p1,p p2,p p3,p p4
  4  where
  5  p1.pn<p2.pn and p2.pn<p3.pn and p3.pn<p4.pn;

表已创建。

已用时间:  00: 00: 00.04
SQL> with k as (select level l from dual connect by level<=:m)
  2  select count(l) from k ,p2
  3  where mod(l,mp)=0;
select count(l) from k ,p2
                        *
第 2 行出现错误:
ORA-01013: 用户请求取消当前的操作


已用时间:  00: 01: 09.01

〇〇

〇〇 发表于 2012-1-7 21:13
用野花先算出质数积的点子更慢
SQL> create table p2 as
  2  select p1.pn*p2.pn*p3.pn*p4.pn mp

因为只要数个数，其实还是应该用筛法，把质数积的倍数依次取掉
比如
2 3 5 7
2 3 5 7 *2
2 3 5 7 *3
2 3 5 7 *4
...
2 5 7 11
2 5 7 11*2
....

〇〇

〇〇 发表于 2012-1-7 21:18
因为只要数个数，其实还是应该用筛法，把质数积的倍数依次取掉
比如
2 3 5 7

还是差不多时间

SQL> select :m-count(*)
  2  from
  3  (
  4  select level pn from dual connect by level<=:m
  5  minus
  6  select mp*l from p2,(select level l from dual connect by level<=:m/2/3/5/7)
  7  where l<=:m/mp);

:M-COUNT(*)
-----------
       9280

已选择 1 行。

已用时间:  00: 00: 02.63

lastwinner

〇〇 发表于 2012-1-7 21:13
用野花先算出质数积的点子更慢
SQL> create table p2 as
  2  select p1.pn*p2.pn*p3.pn*p4.pn mp

你没建索引？

〇〇

全都加上索引也没用，本来是个全表扫描操作
SQL> create index p2mp on p2(mp);

索引已创建。

已用时间:  00: 00: 00.03
SQL> with k as (select level l from dual connect by level<=:m)
  2  select count(l) from k ,p2
  3  where mod(l,mp)=0;
select count(l) from k ,p2
                        *
第 2 行出现错误:
ORA-01013: 用户请求取消当前的操作


已用时间:  00: 00: 18.37

SQL> print :m

         M
----------
    100000

SQL> create table k as select level l from dual connect by level<=100000;

表已创建。

已用时间:  00: 00: 00.18
SQL> create index kl on k(l);

索引已创建。

已用时间:  00: 00: 00.10
SQL> select count(l) from k ,p2
  2  where mod(l,mp)=0;
select count(l) from k ,p2
                     *
第 1 行出现错误:
ORA-01013: 用户请求取消当前的操作


已用时间:  00: 00: 22.78

SQL>

〇〇

〇〇 发表于 2012-1-7 21:18
因为只要数个数，其实还是应该用筛法，把质数积的倍数依次取掉
比如
2 3 5 7

如果用plsql,就可以算出范围之内的2 3 5 7倍数有多少个，2 3 5 11 倍数有多少个
但是会算重复，比如2 3 5 7*11 和 2 3 5 11 *7 。。。

newkid

怎么会重复？你自己可以控制顺序吗，就是几个嵌套循环。
PLSQL的好处是可以利用前面的计算结果。利用对数可以把乘法变成加法。题目没要求具体数字，所以知道范围就可以知道个数。如果下周有空我来写一个。

newkid

#347, 相当于一个斜面 z=x*lg1+y*lg2, 找出正整数坐标(x,y)在这个面上的投影，其中最靠近天花板 z=log(n)的一点。我的那个子查询是把那些边缘点都比较一遍。本来想看看这些点连成的折线是否单调递增或递减，这样只需取两端就可以了，但是我把10万内的点查了一下就发现几个锯齿形的。如果能找到这个公式就好了，这个对数学专业的应该是小菜一碟吧？